[LeetCode] Set Matrix Zeroes 풀이

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

Set Matrix Zeroes - LeetCode

문제요약

2차원 배열이 있을 때 어떤 원소가 0이라면 그 원소가 속한 행과 열의 값을 모두 0으로 바꾸되 추가적인 배열을 사용하지 말것(Constant Space)

 

행의 크기가 n, 열의 크기가 m 일 때 단순히 맨 가장자리부분, 첫 행과 첫 열을 그 행과 열이 바뀌어야하는지 아니면 안 바뀌어도 되는지 확인하는 변수로 쓸 수 있다. 위의 방법으로 (0,0) ~(n-1, m-1)의 배열에서 (1,1) ~(n-1,m -1)의 부분 배열을 다룰 수 있게 된 것이다. 그리고 각 첫 행과 첫 열이 0인지는 bool 변수 하나씩 두어서 처리하면 된다.

 

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        bool col = false;
        bool row = false;
        for(int i=0;!row && i<n;++i) if(!matrix[i][0]) row = true;
        for(int i=0;!col && i<m;++i) if(!matrix[0][i]) col = true;
        for(int i=1;i<n;++i){
            for(int j=1;j<m;++j) {
                if(!matrix[i][j]) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for(int i=1;i<n;++i) {
            if(!matrix[i][0]){
                for(int j=1;j<m;++j) {
                    matrix[i][j] = 0;
                }       
            }
        }
        for(int i=1;i<m;++i) {
            if(!matrix[0][i]){
                for(int j=1;j<n;++j) {
                    matrix[j][i] = 0;
                }       
            }
        }
        if(row) for(int i=0;i<n;++i) matrix[i][0] = 0;
        if(col) for(int i=0;i<m;++i) matrix[0][i] = 0;
    }
};