As Far from Land as Possible

바로 전에 풀었던 문제와 상당히 비슷한 결이다. 이번에는 0이 물이고 1이 지상일때 가장 지상이랑 멀리 위치한 물을 찾으면 된다.

Shortest Path 문제는 보통 BFS 류가 많이 사용되는데..이 문제와 전에 문제에 특징은 한 포인트에서 찾는게 아니고 여러 포인트에서 가장 짧은 루트를 찾아야 한다.

만약 0에서부터 탐색을 시작하면은 탐색 범위가 0을 또 포함 해야하기 때문에 중복이 되고 더 커진다. 그렇기 때문에 1에서 시작해서 반대로 탐색하는게 훨씬 더 효율적이다.

전 문제와 비슷하게 풀었고 빠르게 풀었다.

class Solution {

struct Node{
    int x, y, dist; 
};
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}}; 
public:
    int maxDistance(vector<vector<int>>& grid) {
        int answer = -1; 
        queue<Node> q; 
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false)); 
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[i].size(); j++){
                if(grid[i][j] == 1){
                    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 >= grid.size() || nY >= grid[0].size() || visited[nX][nY]) continue; 

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

        return answer; 
        
    }
};