16928번 뱀과 사다리 게임

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

---

아이디어

뱀과 사다리를 딕셔너리에 넣고 BFS를 돌면서 뱀이나 사다리 칸에 도착하면 우선 옮기고 옮긴 칸이 방문하지 않은 칸인지 확인하고 +1을 해준다.

내가 간과했던 점은

1 1
3 98
98 15

3 -> 98(사다리) -> 15(뱀) 이러한 경우이다.
사다리를 타고 간 곳에 뱀이 있을 수도 있고 또 사다리가 있을 수도 있다.

코드

import sys
from collections import deque
input = sys.stdin.readline

def bfs():
    queue = deque()
    queue.append(1)

    while queue:
        x = queue.popleft()
        if x == 100:
            return graph[100]

        for i in range(1, 7):
            nx = x + i
            if nx < 1 or nx > 100: continue # 범위 밖
            if graph[nx] != 0: continue

            if nx in ladder.keys(): # 사다리 확인
                nx = ladder[nx]
            elif nx in snake.keys(): # 뱀 확인
                nx = snake[nx]
            if graph[nx] == 0:
                queue.append(nx)
                graph[nx] = graph[x]+1


n, m = map(int,input().split()) # n: 사다리, m: 뱀

ladder, snake = {}, {}
for i in range(n):
    a, b = map(int, input().split())
    ladder[a] = b
for i in range(m):
    a, b = map(int, input().split())
    snake[a] = b

graph = [0]*101
print(bfs())