C++:: 프로그래머스 < 게임 맵 최단거리 >

전형적인 최단거리를 구하는 문제이다. bfs를 사용하여 풀었다.

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

int solution(vector<vector<int>> maps)
{
    int n = maps.size(), m = maps[0].size();
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};// 시계방향
    vector<vector<int>> vis(n, vector<int>(m, -1));
    
    queue<pair<int,int>> q;
    q.push({0,0});
    vis[0][0] = 1;// 초기 설정
    
    while (!q.empty()) {
        pair<int,int> cur = q.front();
        q.pop();
        for (int dir=0; dir<4; dir++) {
            int nx = cur.first + dx[dir], ny = cur.second + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;// 맵 넘어가면
            if (!maps[nx][ny] || vis[nx][ny] > 0) continue;// 이미 방문 했거나, 벽이면
            vis[nx][ny] = vis[cur.first][cur.second] + 1;
            q.push({nx, ny});
        }
    }
    
    return vis[n-1][m-1];
}