[C++] 뱀과 사다리 게임 (백준 16928번)

https://www.acmicpc.net/problem/16928

 

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int move[111];
    for (int i = 0; i < 111; i++) move[i] = i;

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n + m; i++) {
        int a, b;
        cin >> a >> b;
        move[a] = b;
    }

    bool vst[111] = {};
    vst[0] = true;
    queue<pair<int, int>> q; // <position, time>
    q.emplace(1, 0);
    vst[1] = true;
    while (1) {
        int pos = q.front().first;
        int t = q.front().second;
        q.pop();
        if (pos == 100) {
            cout << t << '\n';
            break;
        }
        for (int i = 1; i < 7; i++) {
            if (move[pos + i] <= 100 && vst[pos + i] == false) {
                q.emplace(move[pos + i], t + 1);
                vst[pos + i] = true;
            }
        }
    }
}

이런 문제를 보고 아직도 너비 우선 탐색이 바로 떠오르지 않는 나는.. 바보일까.. move라는 배열에 1부터 100까지 쭉 담아놓고 뱀/사다리가 연결되어 있는 칸은 최종적으로 도착하는 칸의 수로 바꿔준다. 이제 만약 n 칸에 도착하면 move[n] 칸으로 간다고 생각하면 된다.

그리고 bfs를 진행하는데, 큐는 현재 칸 위치와 시간을 둘 다 포함하도록 했다. 그래서 최종으로 이동하는 칸이 100 이하이고 아직 방문 안 한 칸이면 큐에 넣어주도록 했다.

move와 vst의 크기를 111으로 한 이유는 최종으로 이동하는 칸이 100 이하인지 확인할 때 move[pos + i]로 확인하니 +6까지 여유있게 포함할 수 있도록 넉넉하게 잡았다. (AC)