Shortest Path in Binary Matrix

그래프 탐색 문제를 풀면서 느낀점.. Shortest distance 와 Shortest Path 는 결이 좀 다른거같다.

여러가지 포인트에서 어느 한지점에 도달하거나.. 아니면 모든 경로에서 동일하게 움직여서 겹칠 필요가 없다면은 visited 배열을 정말 방문 목적으로 사용해도 되는게 Shortest distance

한 포인트에서 특정 포인트까지 이동 해야하는데... 그 경로가 서로 겹치는게 영향이 있을 경우 Visited 배열을 방문 목적이 아닌 다익스트라처럼 거리를 엄두해서 확인 하는게 Shortest Path 인거 같다.

그런 의미에서 이번 문제도 굉장히 빠르게 풀었다.

class Solution {

struct Node{
    int x, y, dist; 
};
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}}; 
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if(grid[0][0] == 1) return -1; 
        vector<vector<int>> visited(grid.size(), vector<int>(grid[0].size(), INT_MAX)); 
        queue<Node> q; 
        q.push({0,0,1}); 
        visited[0][0] = 1; 

        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() || grid[nX][nY] == 1) continue; 

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

        
        return visited[grid.size()-1][grid[0].size()-1] == INT_MAX ? -1 : visited[grid.size()-1][grid[0].size()-1];
    }
};