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

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

BFS 알고리즘 적용

 

#include<vector>
#include<queue>
using namespace std;

int dirX[4] = {0,0,-1,1};
int dirY[4] = {-1,1,0,0};


int solution(vector<vector<int> > maps)
{
    int answer = -1;
    int i=0, j=0;
    int n= maps.size();
    int m= maps[0].size();
    queue<pair<int,int>> move;
    vector<vector<bool>> visit(n, vector<bool>(m,false));
    
    visit[0][0] = true;
    move.push({0,0});
    while(!move.empty()){
        int x = move.front().first;
        int y = move.front().second;
        int dist = maps[x][y];
        move.pop();
        
        for(i=0; i<4; i++) {
            int ux = x + dirX[i];
            int uy = y + dirY[i];    
            
            if(ux < 0 || uy < 0 || ux >= n || uy >= m 
               || maps[ux][uy] == 0
              || visit[ux][uy] == true)
                continue;

            move.push({ux,uy});
            maps[ux][uy] = dist + 1;
            visit[ux][uy] = true;
        }
    }
    
    if (visit[n-1][m-1])
        answer = maps[n-1][m-1];
    return answer;
}