[leetcode 73] Set Matrix Zeroes

Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

Follow up:

• A straight forward solution using O(mn) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?

 

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

 

Constraints:

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

문제 풀이:

첫번째 접근: 한바퀴 배열을 돌면서 0인 좌표를 큐나 set에 담아둔다음 각각 처리하기

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        queue<pair<int, int>>q;
        
        for(int i=0; i<m; i++){

            for(int j=0; j<n; j++){
                if(matrix[i][j] == 0){
                    q.push(make_pair(i,j));
                }
            }
        }
        
        while(!q.empty()){
            int fr_row = q.front().first;
            int fr_col = q.front().second;
            
            q.pop();
            
            int left = fr_col -1;
            int right = fr_col+1;
            int up = fr_row -1;
            int down = fr_row +1;
            
            while(left > -1){
                matrix[fr_row][left] = 0;
                left--;
            }
            while(up > -1){
                matrix[up][fr_col] = 0;
                up--;
            }
            while(right <n){
                matrix[fr_row][right] = 0;
                right++;
            }
            while(down <m){
                matrix[down][fr_col] = 0;
                down++;
            }
        }
    }
};

 

두번째 접근: 

 추가적인 공간을 사용하지 않기 위해 사용하는 방법이다.

1. 첫번째 row와 첫 번째 col을 체크하여 각각에 0이 있는지 확인한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

2. 위에서 체크한 경계 배열을 제외하고 0이 있으면 해당 위치의 첫번째 row, col에 표시해준다.

 

 

 

 

 

 

 

 

 

 

 

 

 

3. 다시 배열을 돌면서 첫번쨰 row와 col에 0이 표시되어 있으면 0을 업데이트한다.

 

 

 

 

 

 

 

 

 

 

 

 

4. 1에서 확인한 flag를 가지고 첫번쨰 row와 col은 따로 업데이트 한다.

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        bool rowFlag = false;
        bool colFlag = false;
        
        // check if first row has any zero
        for(int i=0; i<n; i++){
            if(matrix[0][i] == 0){
                cout<<"true";
                colFlag = true;
                break;
            }
        }
        
        //check if first col has any zero
        for(int i=0; i<m; i++){
            if(matrix[i][0] == 0){
                rowFlag = true;
                break;
            }
        }
        
        
        // 안쪽에 0이 있다면 바깥쪽에 표기
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(matrix[i][0]==0 || matrix[0][j]==0){
                    matrix[i][j] = 0;
                }
            }
        }
        
        if(colFlag){
            for(int i=0; i<n; i++){
                matrix[0][i] = 0;
            }
        }
        
        if(rowFlag){
            for(int i=0; i<m; i++){
                matrix[i][0] = 0;
            }
        }
        
       
    }
};