[LeetCode] 73. Set Matrix Zeroes

문제

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

73. Set Matrix Zeroes는 m x n 행렬에서 matrix[i][j]가 0인 경우 행 i와 열 j를 모두 0으로 채우는 문제다. 이때 공간 복잡도는 $O(N^2)$보다 작아야한다.

참고

제자리(In-place) 알고리즘에 관해 찾아봤는데, 어떤 곳에서는 추가 공간이 상수항이어야 하고, 다른 곳에선 입력값에 비해 충분히 무시할 수 있다면 상수항이 아니여도 한다고 한다. 그래서 나는 본 문제의 공간 복잡도를 $O(N^2)$가 되도록 해결했다.

BCR(Best Conceivable Runtime)

행렬의 원소가 0인지 아닌지 판단해야하기 때문에 모든 원소를 탐색해야한다. 그러므로 $O(NM)$.

풀이 1

첫 번째 방법은 어떤 행과 열을 0으로 채울지 기록하는 배열들을 사용한 방법이다.

class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        boolean[] rows = new boolean[n];
        boolean[] cols = new boolean[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0) {
                    rows[i] = true;
                    cols[j] = true;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (rows[i]) {
                for (int j = 0; j < m; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            if (cols[i]) {
                for (int j = 0; j < n; j++) {
                    matrix[j][i] = 0;
                }
            }
        }
    }
}

행렬 탐색 시 matrix[i][j]가 0이면 rows[i]와 cols[i]를 true로 설정하고, 이후 rows와 cols에 기록된 행과 열을 0으로 채웠다. 시간 복잡도는 $O(NM)$, 공간 복잡도는 $O(N+M)$이다.

풀이 2

두 번째 방법은 첫 번째 방법에서 했던 것을 matrix[0][:]와 matrix[:][0]에 기록하여 추가적인 공간을 사용하지 않는 방법이다. 만약 matrix[i][j] == 0라면 이를 matrix[i][0]과 matrix[0][j]를 0으로 설정하는 것이다.

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean hasOneInRow = false;
        boolean hasOneInCol = false;
        for (int c = 0; c < n; c++) {
            if (matrix[0][c] == 0) {
                hasOneInRow = true;
                break;
            }
        }
        for (int r = 0; r < m; r++) {
            if (matrix[r][0] == 0) {
                hasOneInCol = true;
                break;
            }
        }
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = 0;
                    matrix[0][c] = 0;
                }
            }
        }
        for (int r = 1; r < m; r++) {
            if (matrix[r][0] == 0) {
                for (int c = 1; c < n; c++) {
                    matrix[r][c] = 0;
                }
            }
        }
        for (int c = 1; c < n; c++) {
            if (matrix[0][c] == 0) {
                for (int r = 1; r < m; r++) {
                    matrix[r][c] = 0;
                }
            }
        }
        if (hasOneInRow) {
            for (int c = 0; c < n; c++) {
                matrix[0][c] = 0;
            }
        }
        if (hasOneInCol) {
            for (int r = 0; r < m; r++) {
                matrix[r][0] = 0;
            }
        }
    }
}

단, 조심해야할 점은 처음에 matrix[0][:]과 matrix[:][0]에 0이 존재했는지 미리 알아둬야 한다는 것이다. 왜냐하면 matrix[i][j] == 0을 판단하면서 matrix[i][0] 또는 matrix[0][j]에 0이 들어가기 때문에, 나중에 matrix[0][:]과 matrix[:][0]를 0으로 채워야 할지 말지 판단할 수 없어지기 때문이다. 시간 복잡도는 $O(NM)$, 공간 복잡도는 $O(1)$이다.