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

• 출처: 프로그래머스 1844
• 분류: DFS/BFS · Lv.2

문제

n×m 격자 맵에서 (0,0)부터 (n-1,m-1)까지 최단 거리를 구한다. 1은 이동 가능, 0은 벽이다. 도달 불가능하면 -1을 반환한다. 거리는 시작 칸 포함 칸 수다.

핵심

가중치 없는 격자 최단 경로 → BFS. 시작점에서 BFS를 돌려 목적지에 처음 도달한 시점의 거리가 답이다.

풀이

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

struct Node { int x, y, dist; };

int solution(vector<vector<int>> maps) {
    int n = maps.size(), m = maps[0].size();
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    vector<vector<bool>> visited(n, vector<bool>(m, false));

    queue<Node> q;
    q.push({0, 0, 1});
    visited[0][0] = true;

    while (!q.empty()) {
        auto [x, y, dist] = q.front();
        q.pop();

        if (x == n - 1 && y == m - 1) return dist;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (visited[nx][ny] || maps[nx][ny] == 0) continue;

            visited[nx][ny] = true;
            q.push({nx, ny, dist + 1});
        }
    }
    return -1;
}

메모

• C++ 구조체 넣기/꺼내기
  • {0, 0, 1}로 Node를 생성하는 것은 aggregate initialization (C++11)이다. 생성자 없이 구조체 멤버 순서대로 값을 넣는다. pair의 {x, y}도 같은 원리다
  • auto [x, y, dist]로 꺼내는 것은 structured bindings (C++17)이다. 구조체, pair, tuple의 멤버를 이름 붙여 분해한다. node.x, node.y 대신 바로 변수로 쓸 수 있다
  • tuple<int,int,int>도 auto [a, b, c]로 바인딩되지만, 필드에 이름이 없어서 선언부만 보면 의미를 알 수 없다. 구조체가 더 명확하다
• visited를 찍는 시점
  • BFS에서 visited는 push할 때 찍어야 한다. pop할 때 찍으면 같은 칸이 중복 push되어 시간 초과가 발생한다
  • 자세한 설명은 BFS에서 visited를 push할 때 찍어야 하는 이유 참고
• BFS 기본 패턴
  • 별도 visited 배열을 두어 maps를 변경하지 않는다. maps가 const여도 동작한다
  • 목적지 도달 즉시 return dist로 빠져나온다. BFS이므로 처음 도달한 시점이 최단이다
  • 큐가 비었는데 목적지에 도달하지 못했으면 -1을 반환한다
  • visited + 큐에 상태를 넘기는 패턴이 BFS의 기본형이다. 입력 배열을 덮어쓰는 트릭은 원본이 필요 없을 때만 가능하고, 대부분의 문제에서는 원본 참조가 필요하므로 이 패턴이 범용적이다
  • DFS로도 탐색은 되지만 최단 거리를 보장하지 않는다. 격자 최단 경로에는 BFS를 쓴다

복잡도

풀이	시간	공간
BFS	O(N·M)	O(N·M)