01 Matrix

되게 인상깊은 문제를 풀어봤다. BFS 문제인데 4방향으로 0이랑 가장 가까운 거리를 담는 문제다.

단순하게 BFS를 생각하기에 좀 고려해야 하는 부분이 있다. 만약에 4방향에서 0이 다 있다라면은 쉽겠지만 1이 여러번 겹쳤을때는 같은 구간을 계속 탐색 해야한다는 안좋은 조건이 있다.

그렇기 때문에 이 문제를 최적화 해서 생각하려면 조금 반대 방향으로 생각해야한다. 어떻게 하면 1만 탐색할 수 있을까? 0에서부터 시작하면 된다.

처음 탐색을 할때 0을 모두 visited 로 만들어주고 0에서부터 시작된 탐색을 하면은 가장 가까운 거리로 1을 표시해줄거라 최적화가 잘되어 문제를 풀 수 있다.

2020년에도 이 문제를 풀었는데 그때는 테스트케이스가 많지 않아서 통과됐지만 다시 풀어보니 생각을 많이 해야하는 문제다.

BFS를 풀때, 짧은 거리 문제에서 발상을 조금 다르게 생각하는것도 좋을거같다.

class Solution {

vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}}; 
struct Node{
    int x, y, dist; 
};
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        vector<vector<int>> matrix(mat.size(), vector<int>(mat[0].size(),0)); 
        vector<vector<bool>> visited(mat.size(), vector<bool>(mat[0].size(), false)); 

        queue<Node> q; 

        for(int i = 0; i < mat.size(); i++){
            for(int j = 0; j < mat[0].size(); j++){
                if(mat[i][j] == 0){
                    q.push({i,j,0}); 
                    visited[i][j] = true; 
                }
            }
        }

        while(!q.empty()){
            int size = q.size(); 
            for(int i = 0; i < size; i++){
                Node node = q.front();
                q.pop(); 
                
                int x = node.x, y = node.y, dist = node.dist; 

                for(pair<int,int>& p : dir){
                    int nX = x + p.first;
                    int nY = y + p.second; 

                    if(nX < 0 || nY < 0 || nX >= mat.size() || nY >= mat[0].size() || visited[nX][nY]) continue; 

                    visited[nX][nY] = true; 
                    matrix[nX][nY] = dist + 1; 
                    q.push({nX,nY,dist+1}); 
                }
            }
        }

        return matrix; 

    }
};