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

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

프로그래머스

 

풀이과정

bfs의 가장 기본 알고리즘이다.  
만약 dist[maps.size() - 1]maps[0].size() - 1] 부분이 0이라면  
도달하지 못했다는 뜻이므로 -1을 리턴해준다.

 

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

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int dist[101][101];

int bfs(int x, int y, vector<vector<int>> maps){
    queue<pair<int, int>> q;
    q.push({x, y});
    dist[x][y] = 1;

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx > maps.size() - 1 || ny < 0 || ny > maps[0].size() - 1)
                continue;
            if(!dist[nx][ny] && maps[nx][ny] == 1){
                q.push({nx, ny});
                dist[nx][ny] = dist[x][y] + 1;
            }
        }
    }
    return dist[maps.size() - 1][maps[0].size() - 1];
}

int solution(vector<vector<int>> maps)
{
    int answer = 0;
    answer = bfs(0, 0, maps);
    if(!answer) answer = -1;
    return answer;
}