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

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

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

 

전형적인 BFS문제 

각 칸마다 카운트를 입력해주고

도착지에 도착했을때 그 카운트가 가장 최소인 값 출력

 

도착지에 도착 못 하면 -1 출력

#include<vector>
#include <queue>
using namespace std;
 
int n;
int m;
int answer = 987654321;
bool visit[101][101];
int cnt[101][101];
 
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };
 
 
void bfs(vector<vector<int> > maps) {
    visit[0][0] = true;
    cnt[0][0] = 1;
    queue<pair<int, int>> q;
    q.push({ 0,0 });
 
    while (!q.empty()) {
        int a = q.front().first;
        int b = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int da = a + dx[i];
            int db = b + dy[i];
 
            if (da >= 0 && db >= 0 && da < n && db < m) {
                if (visit[da][db] == false && maps[da][db] == 1) {
                    cnt[da][db] = cnt[a][b] + 1;
                    q.push({ da,db });
                    visit[da][db] = true;
 
                    if (da == n - 1 && db == m - 1) {
                        answer = min(answer, cnt[da][db]);
                    }
                }
            }
 
        }
    }
    if (answer == 987654321) answer = -1;
}
 
int solution(vector<vector<int> > maps)
{
    n = maps.size();
    m = maps[0].size();
 
    bfs(maps);
 
    return answer;
}