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

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

프로그래머스

문제 유형 : BFS

난이도 : Level 2

 

문제

(1, 1)에서 시작하는 캐릭터를 (n,m)으로 보내는데 필요한 거리를 구하시오(단, 캐릭터는 상하좌우만 이동가능하다)

불가능한 경우 -1을 반환한다

 

입력

2차원 배열 maps가 주어지고, 벽은 0 ,갈 수 있는 지역은 1로 표시된다.

n, m은 1 이상 100 이하이다. n과 m 모두 1인 경우는 존재하지 않는다.

 

출력

필요한 거리를 출력. 단, 불가능한 경우 -1 반환.

 

 

풀이

흔한 BFS의 유형 중 하나이다. 상하좌우 중 갈 수 있는 곳을 큐에 넣으면 된다. 상하좌우를 한 번 돌면, 거리를 1 늘린걸로 간주하고 다음 큐를 계속 빼면 된다. n,m에 도달하면 탐색을 멈추고 값을 반환시키면 된다.

큐가 비면, 다 탐색했음에도 n, m에 도달하지 못했다는 뜻으로 큐가 끝나고 난 뒤 -1을 반환시키면 된다.

 

코드(C++)

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

vector<int> dx = {-1, 1, 0, 0};
vector<int> dy = {0, 0, -1, 1};

int bfs(int n, int m, vector<vector<int>> maps) {
    int distance = 1;
    int x;
    int y;
    deque<vector<int>> q;
    q.push_back({0, 0});
    while (!q.empty()) {
        int q_size = q.size();
        for (int i = 0; i < q_size; i++) {
            x = q.front().at(0);
            y = q.front().at(1);
            q.pop_front();
            if (x == n-1 && y == m-1) {
                return distance;
            }
            for (int j = 0; j < 4; j++) {
                int nx = x + dx.at(j);
                int ny = y + dy.at(j);
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] == 1) {
                    q.push_back({nx, ny});
                    maps[nx][ny] = distance + 1;
                }
            }
        }
        distance++;
    }
    return -1;
}

int solution(vector<vector<int>> maps) {
    int n = maps.size();
    int m = maps.at(0).size();
    int answer = bfs(n, m, maps);
    return answer;
}