BOJ 16928. 뱀과 사다리 게임

게시 2020/04/23 수정 2026/10/07 작성자 August

조회 8 분 읽는 시간

문제링크 : https://www.acmicpc.net/problem/16928

BOJ 16928 뱀과 사다리 게임은 게임 문제처럼 보이지만, 실제로는 최단 횟수를 구하는 BFS 문제다. 각 칸을 정점으로 보고, 주사위 1~6 이동을 간선으로 보면 구조가 선명해진다.

문제를 내 말로 줄이면 이렇다. 1번부터 100번까지 칸이 있는 보드에서 1번 칸에서 출발해 주사위를 굴려 나온 수만큼 앞으로 간다. 도착한 칸이 사다리의 시작이면 사다리 끝으로 올라가고, 뱀의 머리면 꼬리로 내려간다. 100번 칸에 도착하기까지 주사위를 굴려야 하는 최소 횟수를 구한다.

문제를 그래프로 바꾸기

정점: 1번부터 100번 칸
간선: 현재 칸에서 주사위 1~6을 더한 다음 칸
사다리/뱀: 도착 즉시 다른 칸으로 이동하는 특수 간선

결국 “1번에서 100번까지 가는 최소 이동 횟수”를 구하는 문제다.

왜 BFS인가

주사위를 한 번 굴리는 행위를 비용 1로 보면, 모든 간선의 비용이 동일하다. 이런 경우 최소 횟수 문제는 BFS가 가장 자연스럽다.

구현의 핵심

사다리와 뱀 정보를 배열이나 맵에 저장한다
현재 칸에서 +1부터 +6까지 이동을 시도한다
이동한 칸에 사다리나 뱀이 있으면 즉시 최종 도착 칸으로 바꾼다
아직 방문하지 않았다면 큐에 넣는다

자주 실수하는 부분

사다리/뱀 이동을 별도 턴으로 계산하는 경우

사다리나 뱀은 추가 턴이 아니라, 도착한 즉시 이동하는 효과다. 즉, 주사위를 한 번 던진 결과 안에 포함되어야 한다.

방문 처리를 늦게 하는 경우

같은 칸이 여러 번 큐에 들어가면 불필요한 탐색이 늘어난다. BFS에서는 보통 큐에 넣는 시점에 방문 처리를 하는 편이 안전하다.

100을 넘는 이동 처리

주사위 결과로 100을 넘으면 이동할 수 없다는 조건을 놓치면 오답이 된다.

참고 풀이 코드

원래 이 글에는 코드가 없어서, 같은 폴더의 다른 풀이와 같은 C++로 참고 풀이를 작성했다. 입력은 첫 줄에 사다리 수와 뱀 수가 오고, 이어서 사다리와 뱀이 각각 “출발 칸, 도착 칸” 한 쌍씩 주어진다고 가정한다. 사다리와 뱀은 이동 방향만 다를 뿐 “a에 도착하면 b로 간다”는 같은 규칙이므로 하나의 배열에 담는다.

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

int main() {
    int n, m;
    cin >> n >> m;

    int jump[101];                    // jump[i]: i번 칸에 도착했을 때 최종 위치
    for (int i = 1; i <= 100; ++i) {
        jump[i] = i;
    }
    for (int i = 0; i < n + m; ++i) { // 사다리 n개, 뱀 m개 모두 "a에서 b로 이동"
        int a, b;
        cin >> a >> b;
        jump[a] = b;
    }

    int dist[101];                    // dist[i]: 1번 칸에서 i번 칸까지 주사위 횟수
    for (int i = 0; i <= 100; ++i) {
        dist[i] = -1;
    }

    queue<int> q;
    dist[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int dice = 1; dice <= 6; ++dice) {
            int next = now + dice;
            if (next > 100) {         // 100을 넘으면 이동할 수 없다
                continue;
            }
            next = jump[next];        // 사다리나 뱀은 같은 턴 안에서 바로 따라간다
            if (dist[next] == -1) {   // 큐에 넣는 시점에 방문 처리
                dist[next] = dist[now] + 1;
                q.push(next);
            }
        }
    }
    cout << dist[100] << '\n';
    return 0;
}

코드 따라가기

jump[i]는 i번 칸에 도착했을 때 최종적으로 서게 되는 칸이다. 처음에는 자기 자신으로 채우고, 사다리와 뱀의 출발 칸만 도착 칸으로 바꾼다. 덕분에 BFS 안에서 “사다리인가, 뱀인가”를 따로 묻지 않고 jump[next] 한 번으로 처리한다.
dist[i]는 1번 칸에서 i번 칸까지의 최소 주사위 횟수이고, -1이면 아직 방문하지 않았다는 뜻이다. 따로 visited 배열을 두지 않고 이 값으로 방문 여부를 함께 표현한다.
큐에서 꺼낸 칸마다 주사위 1부터 6까지를 시도한다. 100을 넘는 칸은 건너뛰고, 도착한 칸은 jump로 바꾼 뒤 처음 방문하는 칸일 때만 큐에 넣는다. 위에서 정리한 세 가지 실수(사다리를 별도 턴으로 세기, 방문 처리 늦추기, 100을 넘는 이동)가 각각 코드의 한 줄씩에 대응한다.
BFS가 끝나면 dist[100]이 답이다.

사다리와 뱀이 하나도 없다면 매번 6칸씩 가는 것이 최선이고, 1번에서 100번까지 99칸이므로 ⌈99 / 6⌉ = 17번이 나온다. 위 코드에 사다리 0개, 뱀 0개를 넣으면 실제로 17이 출력된다.

복잡도

정점이 100개, 정점마다 간선이 최대 6개이므로 BFS는 정점 수와 간선 수에 비례하는 O(100 + 600)만큼 일한다. 보드 크기가 고정이라 입력 크기와 상관없이 사실상 상수 시간이다. BFS 자체의 동작은 너비 우선 탐색(BFS)에 정리했다.

정리

이 문제의 포인트는 게임 규칙을 그대로 따라가려는 것보다, 이를 가중치가 없는 최단 거리 그래프 문제로 치환하는 데 있다. BFS를 떠올릴 수 있으면 구현은 비교적 단순해진다.

ProblemSolving, BOJ