[프로그래머스][level2][C++][BFS] 찾아라 프로그래밍 마에스터 - 게임 맵 최단거리 - 컴도리돌이

코딩테스트 연습 - 게임 맵 최단거리

 

• N * M 행렬에서 최단 거리를 보장해주는 탐색 알고리즘인 BFS를 사용하였다.
• 단순히 N*M의 범위를 넘지 않고 벽이 아닌 곧이 있을 경우 해당 값을 큐에 삽입 후 좌표의 값을 1 증가시켰다.
• 최종적으로 반환 값은 N*M 좌표의 값을 반환시켰다. 하지만 해당 값이 1인 경우 모든 벽에 둘러 쌓여서 탐색을 하지 못한 경우이기에 -1 값을 반환하도록 설정하였다.

#include<vector>
#include<queue>

using namespace std;

int answer =0;

int solution(vector<vector<int> > maps)
{
    int dx[] = {-1,0,1,0};
    int dy[] = {0,1,0,-1};

    queue<pair<int,int>> q;
    q.push({0,0});

    while(!q.empty())
    {
        for(int i=0; i<4;i++)
        {
            int nx = q.front().first + dx[i];
            int ny = q.front().second + dy[i];
            if(nx >= 0 && nx <= (maps.size() -1) && ny >= 0 && ny <= (maps[i].size() -1) && maps[nx][ny] == 1)
            {
                q.push({nx,ny});
                maps[nx][ny] = maps[q.front().first][q.front().second] + 1;
            }
        }
        q.pop();
    }

    return maps[maps.size()-1][maps[0].size()-1] == 1 ? -1 : maps[maps.size()-1][maps[0].size()-1];
}