백준 16928 뱀과 사다리 게임 / python

문제 : 16928

풀이 point

사다리와 뱀의 시작위치와 도착위치를 딕셔너리에 저장한다.
bfs를 활용하여 탐색을 하고 거리를 갱신한다.

참고로 이차원 배열이 아니라 일차원으로 풀면된다. (좌표가 따로 없다)

풀이 방법

큐에 위치 값을 넣기 전에 다음 위치가 딕셔너리에 있다면 사다리 혹은 뱀이 그 위치에 있는 것이니 도착 위치를 큐에 삽입해줘야 한다.

중요한 점은 뱀 혹은 사다리를 타서 도착한 위치가 이미 방문한 위치라면 거리를 갱신하지 않도록 해야한다. (거리 갱신 위치 주의)

풀이 코드

from collections import deque

def bfs():
  while Q:
    x = Q.popleft()
    for i in range(1, 7):
      nx = x + i
      if nx > 100:
        continue
      if nx in ladderSnake:
        nx = ladderSnake[nx]
      if dist[nx] != -1:
        continue
      
      dist[nx] = dist[x]+1
      if nx == 100:
        print(dist[100])
        return
      Q.append(nx)

N, M = map(int, input().split())

ladderSnake = {}
dist = [-1]*101

Q = deque()
Q.append(1)
dist[1] = 0
for _ in range(N):
  x, y = map(int, input().split())
  ladderSnake[x] = y

for _ in range(M):
  u, v = map(int, input().split())
  ladderSnake[u] = v

bfs()