프로그래머스) Lv4 - 게임 맵 최단거리

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

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

BFS로 풀이하였습니다.

---

C++ 소스 코드

#include <vector>
#include <queue>
using namespace std;
const int dx[] = {0,0,-1,1}, dy[]={-1,1,0,0};
int dist[101][101];
int solution(vector<vector<int> > maps){
    dist[0][0]= 1;
    int n = maps.size()-1;
    int m = maps[0].size()-1;
    queue<pair<int, int> > q;
    q.push(make_pair(0,0));
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (x == n && y ==m){
            return dist[x][y];
        }
        for(int i=0;i<4;i++){
            int nx = x+dx[i], ny = y+dy[i];
            if (nx <0 || nx >n || ny <0 || ny > m) continue;
            if (maps[nx][ny]==0 || dist[nx][ny]!=0) continue;
            dist[nx][ny]= dist[x][y]+1;
            q.push(make_pair(nx,ny));
        }
    }
    return -1;
}