골드5 뱀과 사다리 게임(16928)

16928번: 뱀과 사다리 게임

이 문제를 풀면서 어떻게 BFS를 통해서 최소 탐색을 할 지 고민을 했습니다. 그래서 1~6을 추가해가면서 100이 되는 것을 확인해야한다고 생각했는데, 어떻게 풀어 나갈지가 가장 문제였다. 기존과 비슷하게 BFS를 진행하고, 각 경우의 수를 나누어 풀어나갔다.

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

def bfs(start):
  q = deque([start])
  visited[start] = 0
  while q:
    v = q.popleft()
    if v == 100: break
    for d in (1,2,3,4,5,6):
      nextD = v + d
      if (0 <= nextD <= 100) and (not visited[nextD]):
        if nextD in ladder.keys():
          nextD = ladder[nextD]
        elif nextD in snake.keys():
          nextD = snake[nextD]
        if not visited[nextD]:
          q.append(nextD)
          visited[nextD] = visited[v] + 1

n, m = map(int, input().split())
visited = [0] * 101 # 이전 단계에 대한 횟수를 저장해놓을 것 + 0이 아니면 방문한걸로 판단
ladder = {int(x[0]): int(x[1]) for x in [input().split() for _ in range(n)]}
snake = {int(x[0]): int(x[1]) for x in [input().split() for _ in range(m)]}
bfs(1)
print(visited[-1])

사다리와 뱀은 딕셔너리를 활용해서 구현을 했습니다. 리스트로 풀면 n시간이지만 딕셔너리는 탐색시간이 줄어들어서 조금의 시간을 줄일 수 있다고 생각했습니다. 그리고 visited리스트를 TF로 넣은게 아니라 횟수로 구현했다. 그렇게 구현하면 0보다 크면 방문했다는 것으로 했습니다. 그 다음에 BFS를 구현했는데 대부분의 BFS와 같이 구현이 되고, 조건문에서 차례로 검사한다.  visited[nextD]를 마지막 if문에서 검사하는 이유는 nextD가 변경되어서 그것 마저 검사해서 큐에 넣어야하기 때문입니다. 이렇게 구현해서 성공했다.