[LeetCode]Set Matrix Zeroes

https://leetcode.com/problems/set-matrix-zeroes/description/

Set Matrix Zeroes - LeetCode

 

문제 분석

m*n matrix에서 0을 만날 때 해당 위치가 들어간 row, col을 모두 0으로 만든 이후의 matrix를 구하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m = len(matrix)
        n = len(matrix[0])
		
        first_row_has_zero = False
        first_col_has_zero = False
        
        # iterate through matrix to mark the zero row and cols
        for row in range(m):
            for col in range(n):
                if matrix[row][col] == 0:
                    if row == 0:
                        first_row_has_zero = True
                    if col == 0:
                        first_col_has_zero = True
                    matrix[row][0] = matrix[0][col] = 0
    
        # iterate through matrix to update the cell to be zero if it's in a zero row or col
        for row in range(1, m):
            for col in range(1, n):
                if matrix[0][col] == 0 or matrix[row][0] == 0:
                    matrix[row][col] = 0
                    
        # update the first row and col if they're zero
        if first_row_has_zero:
            for col in range(n):
                matrix[0][col] = 0
        
        if first_col_has_zero:
            for row in range(m):
                matrix[row][0] = 0

접근 방법

1. m과 n, first_row_has_zero, first_col_has_zero와 같은 변수를 설정합니다.
2. grid를 이중 순회합니다.
3. 만약 순회도중 0을 만난다면
   1. row가 0일 때라면 first_row_has_zero를 True로 설정합니다.
   2. col이 0일 때라면 first_col_has_zero를 True로 설정합니다.
   3. 그리고 등장한 위치에서 row가 0, col이 0이 되는 지점을 0으로 설정합니다.
      (0 인덱스의 row, col을 어떠한 Flag로 사용하는 것입니다)
4. 다시한번 이중 순회하면서 위에서 지정한 Flag를 만난다면 0으로 할당하고 아니라면 유지합니다.
5. 첫번째 row에 0이 있다면 첫번째 row를 모두 0으로 변경합니다.
6. 첫번째 col에 0이 있다면 첫번째 col을 모두 0으로 변경합니다.

이 문제를 푸는 방법은 여러가지가 있을 수 있습니다. 하지만 문제의 제약조건으로 in place, constant space가 존재합니다.

그래서 공간 복잡도를 줄이기 위해서 0이 등장했을 때 등장한 row와 col의 첫번째 요소를 Flag로 설정합니다. (0으로 변경하기)

또한, first_row_has_zero, first_col_has_zero 두개의 변수만으로 인덱스가 0인 row, col들의 변경 여부를 파악할 수 있습니다.

즉, row나 col이 0인 것들 / 나머지 것들을 분리해서 업데이트 하는 것입니다.

 

가장 쉬운 방법은 2차원 grid를 복사하여 풀이하는 방법이겠지만 문제의 제약조건은 해결할 수 없습니다. 그래서 위와 같은 Flag를 사용했습니다.

 

방법을 생각해내기가 매우 어려워 솔루션을 참고해 풀이했습니다.