BOJ 16928. 뱀과 사다리 게임

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

문제를 그래프로 바꾸기

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

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

왜 BFS인가

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

구현의 핵심

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

자주 실수하는 부분

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

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

방문 처리를 늦게 하는 경우

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

100을 넘는 이동 처리

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

정리

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