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

문제가 상당히 길다.

하지만 이전 문제들처럼 그냥 거리계산만 하면 된다.
기본 BFS문제에 속하는 문제이다.

맵의 시작 부분을 큐에 넣음과 동시에 BFS를 시작한다.
도달하지 않은 곳의 dist 값은 -1이고, 시작점으로부터의 거리가 dist 값에 업데이트된다.

생각해 주어야 할 것은, (n-1,m-1)번째 dist값이 -1이라면 길이 막혀서 갈 수 없는 곳이므로 -1을 출력한다는 것과, 시작점의 dist을 0으로 설정하였으므로 마지막에 값을 저장할 때 +1을 해줘야한다는 것이다.

#include<queue>
#include<vector>
#include <bits/stdc++.h>

using namespace std;
int dist[102][102];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int solution(vector<vector<int> > maps)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n=maps.size();
    int m=maps[0].size();
    int answer = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dist[i][j]=-1;
        }
    }
    queue<pair<int,int>> q;
    q.push({0,0});
    dist[0][0]=0;
    while(!q.empty()){
        auto cur = q.front();
        q.pop();
        for(int dir=0;dir<4;dir++){
            int nx=cur.first+dx[dir];
            int ny=cur.second+dy[dir];
            if(nx>=n||ny>=m||nx<0||ny<0) continue;
            if(dist[nx][ny]!=-1 || maps[nx][ny]==0) continue;
            dist[nx][ny]=dist[cur.first][cur.second]+1;
            q.push({nx,ny});
        }
    }
    if(dist[n-1][m-1]==-1) answer = -1;
    else answer= dist[n-1][m-1]+1;
    return answer;
}