[백준 16928번] 뱀과 사다리 게임 (Python/파이썬)

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

16928번: 뱀과 사다리 게임

이런 유형의 문제를 BFS로 다루는 것을 많이 해봤기 때문에 알고리즘은 바로 떠올렸다.

하지만 뱀이나 사다리에 도착했을 때 바로 이동해야하는데 이동하지 않고 방문여부를 따지는 코드를 짜서 살짝 헤맸다.

뱀이나 사다리에 도착했을 때 바로 이동시키니 문제는 바로 풀렸다.

평범한 BFS문제이다.

 

코드는 다음과 같다.

import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int,input().split())
ladder = {}
snake = {}
for _ in range(N):
  x, y = map(int,input().split())
  ladder[x] = y
for _ in range(M):
  u, v = map(int,input().split())
  snake[u] = v
visited = [False] * 101
visited[1] = True
map = [0] * 101

def BFS(e):
  queue = deque([])
  queue.append(e)
  while queue:
    now_pos = queue.popleft()
    for i in range(1,7):
      tmp_pos = now_pos + i
      if tmp_pos == 100:
        return map[now_pos] + 1
      
      if tmp_pos in ladder:
        tmp_pos = ladder[tmp_pos]
      elif tmp_pos in snake:
        tmp_pos = snake[tmp_pos]
      if not visited[tmp_pos]:
        visited[tmp_pos] = True
        map[tmp_pos] = map[now_pos] + 1
        queue.append(tmp_pos)

print(BFS(1))