Leetcode - 542. 01 Matrix

문제

각각의 셀마다 가장 가까운 0의 거리는?

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

아이디어

2. Idea

• brute-force search mat from 0 to n -> O(N^2) (N=m*n)
• using Queue -> O(N) / O(N)
  문제를 보면 0주변은 1, 1주변은 2 이런식으로 증가된다. 너비우선으로 값이 증가되는 구조다. 즉 일종의 BFS형태. 이런 형태는 Queue를 사용하는게 국률이다. 기억하기!!
• possible O(N) / O(1)? -

해결 O(N)/ O(N) (N=m*n)

• 먼저 0인 좌표를 queue에 push
• pop 하고 주변값이 1이면 pop한 값에 + 1한값을 더함, 그 좌표는 push
• 한번 queue에 push했던 좌표는 visited체크,
• 이것을 반복한다.

class Solution {
    std::queue<pair<int, int>> q;
    int rsize;
    int csize;
    vector<vector<int>> visit; // 수행속도는 함수 매개변수로 넘기는 방식이 더 빨랐음.
    
    void inc_count_push(vector<vector<int>> &mat, int r, int c) {
        int pos_val = mat[r][c];
        
        // check 4 direction from pop position
        // if on 4 each value is 1 -> increase by pos_val + 1
        // then push it
        if (r-1 >= 0 && visit[r-1][c] == 0 && mat[r-1][c] == 1) {
            mat[r-1][c] = pos_val + 1;
            q.push(make_pair(r-1, c));
            visit[r-1][c] = 1;
        }
        if (r+1 < rsize && visit[r+1][c] == 0 && mat[r+1][c] == 1) {
            mat[r+1][c] = pos_val + 1;
            q.push(make_pair(r+1, c));
            visit[r+1][c] = 1;
        }
        if (c-1 >= 0 && visit[r][c-1] == 0 && mat[r][c-1] == 1) {
            mat[r][c-1] = pos_val + 1;
            q.push(make_pair(r, c-1));
            visit[r][c-1] = 1;
        }
        if (c+1 < csize && visit[r][c+1] == 0 && mat[r][c+1] == 1) {
            mat[r][c+1] = pos_val + 1;
            q.push(make_pair(r, c+1));
            visit[r][c+1] = 1;
        }
    }
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        rsize = mat.size();
        csize = mat[0].size();
        //vector<vector<int>> visit(rsize, vector<int> (csize, 0)); 
        visit = vector<vector<int>> (rsize, vector<int> (csize, 0));
        
        for (int i = 0; i < rsize; i++) {
            for (int j = 0; j < csize; j++) {
                if (mat[i][j] == 0)
                    q.push(make_pair(i, j));
            }
        }
        while (!q.empty()) {
            pair<int, int> pos = q.front();
            q.pop();
            inc_count_push(mat, pos.first, pos.second);
        }
        return mat;
    }
};

2차원 vector 초기화 방법

숙지하자.

vector<vector<int>> visit(rsize, vector<int> (csize, 0)); 

• 전역변수 선언, 초기화는 로컬에서

vector<vector<int>> visit; //전역 선언
visit = vector<vector<int>> (rsize, vector<int> (csize, 0)); //초기화