[C/C++] programmers Level 2 게임 맵 최단거리 - 참고

 

 

 

 

코드

#include <vector>
#include <queue> // 큐 -> BFS 

using namespace std;

bool visited[101][101]; // 방문 체크 -> maps : n x m 크기 (1<=n,m<=100)
int bfsmap[101][101]; // BFS 진행하며 거리 체크

int x[4]={1,-1,0,0}; // x축
int y[4]={0,0,1,-1}; // y축

queue<pair<int, int>> q; // int : y, int : x

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    
    int col=maps.size(); // 행
    int row=maps[0].size(); // 열
    
    // 시작점 대입
    q.push({0,0});
    visited[0][0]=true;
    bfsmap[0][0]=1;
    
    // BFS
    while(!q.empty()){
        int qy=q.front().first;
        int qx=q.front().second;
    
        q.pop();
        
        for(int i=0;i<4;i++){ // 방문한 곳을 기준으로 4가지 방향에 있는 곳들 예약 처리
            int ny=qy+y[i];
            int nx=qx+x[i];
            
            if(nx<0 || nx>=row || ny<0 || ny>=col){ // 움직일 수 있는 범위를 벗어난 경우
                continue;
            }
            
            if(visited[ny][nx]){ // 방문한 경우
                continue;
            }
            
            if(maps[ny][nx]==0){ // 막혀있는 경우
                continue;
            }
            
            q.push({ny,nx});
            visited[ny][nx]=true;
            bfsmap[ny][nx]=bfsmap[qy][qx]+1; // 최단 거리 업데이트 -> 방문 노드에서 +1 하면 최단거리
        }
    }
    
    if(!visited[col-1][row-1]){ // 도착지가 한번도 큐에 들어갔던적이 없다면 -1 리턴
        answer=-1;
    }else{
        answer=bfsmap[col-1][row-1]; // 최단 경로
    }
    
    return answer;
}