[16928] 뱀과 사다리 게임

처음에 bfs인가 싶었는데 또 완전탐색인가 싶기도 했음

결국 모르겠어서 확인하니까 bfs가 맞았음..

제미나이의 도움을 받았다.

미로탐색이나 토마토 같은 정석의 큐브가 아니라 감이 안 온 문제였다. 

---

문제 이해를 위한 설명을 이렇게 해줬다.

1. BFS는 '동심원'이 퍼져나가는 것과 같습니다

미치광이 주사위 도박사가 1번 칸에 서서, 한 번에 분신술을 써서 6명을 만든다고 상상해 보세요.

• 0초 (시작): 1번 칸에 나 혼자 있음. (큐: [1])
• 1초 (첫 번째 주사위): 내 분신 6명이 주사위 1, 2, 3, 4, 5, 6을 들고 각각의 칸으로 달려갑니다.
  • 만약 3번 칸에 사다리가 있다면? 3번으로 간 분신은 즉시 사다리 끝인 20번 칸으로 순간이동합니다.
  • 이제 1초 뒤에 분신들이 서 있는 곳들은 [2, 20, 4, 5, 6, 7]이 됩니다. 이 칸들은 모두 **"주사위 1번 만에 올 수 있는 곳"**입니다.
• 2초 (두 번째 주사위): 이제 저 6곳에 있는 분신들이 동시에 또 주사위를 6개씩 굴려 사방으로 흩어집니다.
  • 이때, 이미 누군가 지나갔던 칸은 무시합니다. (이게 visited 체크입니다.)
  • 새롭게 도착한 칸들은 모두 **"주사위 2번 만에 올 수 있는 곳"**이 됩니다.

이렇게 "1번 만에 갈 수 있는 모든 곳 → 2번 만에 갈 수 있는 모든 곳 → 3번 만에..." 순으로 땅따먹기를 하듯 퍼져나가는 것이 BFS입니다.

---

2. 뱀과 사다리는 '지름길' 혹은 '함정'일 뿐

보드판을 위에서 내려다보면, 사다리와 뱀은 그냥 **특정 칸에 발을 들이자마자 발동하는 강제 워프(Warp)**입니다.

• 사다리: 8번 칸에 도착했는데 사다리가 80번으로 연결된다면, 8번 칸에 발을 딛는 순간 그 분신은 80번에 소환됩니다. 그 분신은 이제 다음 턴에 80번에서 주사위를 굴릴 준비를 합니다.
• 뱀: 90번 칸에 도착했는데 뱀이 10번으로 연결된다면, 90번에 발을 딛자마자 10번으로 추락합니다.

중요한 건, 사다리를 타든 뱀을 타든 주사위는 이미 1번 굴린 상태라는 점입니다. 주사위 한 번으로 결과적으로 80번에 가든 10번에 가든, 이동 횟수는 똑같이 +1입니다.

---

3. 왜 100번에 가장 먼저 도착한 놈이 정답인가?

분신들이 동시에 출발해서 사방으로 퍼지고 있죠? 100번이라는 목적지에 가장 먼저 깃발을 꽂는 분신이 있을 겁니다. 그 분신이 100번에 도착한 순간이 바로 "최단 횟수"입니다.

뒤늦게 뱀을 돌고 돌아 도착한 다른 분신들은 100번에 이미 깃발이 꽂혀 있는 것을 보고(방문 체크), 그들의 기록은 무시하게 됩니다.

---

 

그래서 헷갈렸던 게 크게 두 개 있는데

1. 방향 탐색이 아니라 경우를 탐색하는 것

주사위를 6번 던진다는 개념이다.

 for i in range(1, 7):

        nt = board[cur] + i

그리고 또 헷갈렸던 점은 

2. 그냥 bfs는 다음 지점을 찍으면 끝인데 여기선 바로 워프를 한다는 점이다.

그래서 next 노드를 한 번더 이동 위치를 잡는다는 부분이 헷갈렸었다.

if 1 <= nt <= 100:

            fn = board[nt]

            if not visited[fn]:

                visited[fn] = True

                cnt[fn] = cnt[cur] + 1

                q.append(fn)

 

[정답]

import sys

from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())

board = [i for i in range(101)]

for _ in range(n + m):

    x, y = map(int, input().split())

    board[x] = y

q = deque([board[1]])

cnt = [0 for i in range(101)]

visited = [False for i in range(101)]

visited[1] = True

while q:

    cur = q.popleft()

    if cur == 100:

        break

    for i in range(1, 7):

        nt = board[cur] + i

        if 1 <= nt <= 100:

            fn = board[nt]

            if not visited[fn]:

                visited[fn] = True

                cnt[fn] = cnt[cur] + 1

                q.append(fn)

print(cnt[100])