[Python] 백준 16928번 : 뱀과 사다리 게임

---

<접근 방법>

1. 어차피 뱀과 사다리는 서로 정확히 겹치는 경우가 없으므로 시작과 끝이 Key - Value로 정해져 있는 것과 마찬가지이므로 info라는 dictionary를 만들어줘서 관리한다.
2. 만일, 뱀이나 사다리를 타고 이동했을 때 방문했던 곳이라면 무한 반복이 가능하므로 visited라는 방문 배열을 하나 만들어 관리한다.
3. BFS방법을 이용해 1~6칸을 이동하는 주사위 굴리기의 최솟값을 구할 수 있을 것 같다.

---

from collections import deque

def bfs():
    q = deque()
    q.append(1) # 1번 칸에서 시작
    cnt = 0 # 주사위 굴리는 횟수
    while q:
        cnt += 1
        for _ in range(len(q)):
            ci = q.popleft()
            for k in range(1, 7):   # 1~6의 주사위 눈
                ni = ci + k
                if ni == 100: return cnt    # 100번째 칸에 도달 시 Return
                if not visited[ni]:
                    visited[ni] = 1 # 도착한 칸 방문처리
                    if ni in info:  # 뱀이나 사다리에 연관있다면 이동
                        q.append(info[ni])
                    else:
                        q.append(ni)
    return 0    # 함수 내에서는 항상 return 값을 갖도록 권고


N, M = map(int, input().split())
info = dict()
visited = [0]*101   # 무한 반복을 피하기 위한 방문처리
visited[1] = 1
for _ in range(N+M):   # 뱀과 사다리를 한 번에 Dictionary에 관리
    s, e = map(int, input().split())
    info[s] = e
print(bfs())

실행시간

이해가 되지 않거나 궁금한 점이 있으면 질문 주세요. 감사합니다.