[프로그래머스] 게임 맵 최단거리 c++

 

풀이

bfs를 이용해 최단거리를 구하는 문제였다.
bfs는 근접 노드를 다 방문하고 depth를 +1 해서 방문하기 때문에 근접 a와 인근한 b,c,d .. 노드들은 depth가 같고 즉 거리가 같다.
그렇기 때문에 b,c,d를 방문한 순서와 상관없이 b,c,d까지의 거리가 같다. ( ex) c,d,b순서대로 방문해도)
한 단계에서 갈 수 있는 모든 노드들을 방문하기 때문에 한 번 방문한 노드의 거리는 노드까지의 최단 경로가 된다.

 

효율성까지 맞기 위해서는이미 거리를 갱신한 노드는 또 거리를 갱신시켜주면 안된다.

b에서 탐색을 해서 d의 최단거리를 3으로 갱신시켜주었다.
c에서 탐색을 할때도 d의 최단거리는 3이 된다. 하지만 이미 갱신을 시켜주었기 때문에 불필요한 작업이 된다.

이는 34번째 줄의 
cnt[dy][dx] ==0을 통해서 체크할 수 있다. cnt는 0으로 초기화되어있기 때문에 0이면 갱신을 안시킨 것이므로 갱신시켜준다.

또는 21번째에 있는 노드 방문 여부를 체크하는 코드를 큐에 넣기 전에 한다면 visit에 걸려 거리를 갱신시키는 코드를 실행시키지 않을 수 있다.

if(visit[dy][dx])
    continue;
if(graph[dy][dx] )
{
    visit[dy][dx] = true;
    node.push({dy,dx});
    graph[y][x]=0;
    cnt[dy][dx]=cnt[y][x]+1;
}

#include<vector>
#include<queue>
#include<iostream>
using namespace std;
int answer =-1;
int n,m;
int dir_y[] = {1,0,-1,0};
int dir_x[] = {0,1,0,-1};
vector<vector<int>> graph;
vector<vector<bool>> visit(101,vector<bool>(101,false));
vector<vector<int>> cnt(101,vector<int>(101,0));

void bfs(int y, int x){
    
    queue<pair<int,int>>node;
    node.push({y,x});
    cnt[0][0]=1;
    while(!node.empty()){
        int y = node.front().first;
        int x = node.front().second;
        visit[y][x]=true;
        node.pop();
        if(y==m && x==n){
            answer=cnt[y][x];
           break; 
        }
        for(int i=0;i<4;i++){
            int dy= y + dir_y[i];
            int dx= x + dir_x[i];
            if(dy<0 || dy>m || dx<0 || dx>n)
                continue;
            if(visit[dy][dx])
                continue;
            if(graph[dy][dx] && cnt[dy][dx] ==0){
                node.push({dy,dx});
                graph[y][x]=0;
                cnt[dy][dx]=cnt[y][x]+1;
            }


        }
    }
      
}
int solution(vector<vector<int> > maps)
{
    m = maps.size()-1;    //세로
    n = maps[0].size()-1; //가로
    graph= maps;
    bfs(0,0);
    return answer;
}