[백준 16928번] 뱀과 사다리 게임 - python

문제 링크

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

16928번: 뱀과 사다리 게임

풀이 

- bfs와 딕셔너리 이용해서 풀었다. 

- ladder 과 snake 딕셔너리를 선언하고 도착한 칸 key, 이동할 칸 value 로 저장 

- 1번부터 100번까지 칸이 존재하고 방문 표시를 위해 visited = [False] * 101 선언 

- 1번 칸에 대하여 bfs 실행 

큐에는 도착한 칸과 주사위를 굴린 횟수 cnt 를 함께 삽입 

도착한 칸 x가 ladder 의 key 에 존재하면, x를 value(ladder[x])로 이동 

도착한 칸 x가 snake의 key에 존재하면, x를 value (ladder[x]) 로 이동 

(이 때 사다리나 뱀을 타고 이동하는 경우는 cnt 가 증가하지 않는다.) 

1부터 6까지 주사위 수 i에 대하여 

x + i 에 방문하지 않았다면 x+i 와 cnt + 1 을 큐에 삽입 

from collections import deque 

def bfs(a):
  visited[a] = True

  q = deque()
  # 도착한 칸과 주사위를 던진 횟수 
  q.append((a,0))

  while q :
    x, cnt  = q.popleft()
    # 100에 도착했으면 주사위를 던진 횟수 return 
    if x == 100:
      return cnt
    # 사다리가 있는 칸이면 사다리를 타고 이동 
    if ladder.get(x) :
        x = ladder[x]
    # 뱀이 있는 칸이면 뱀을 타고 이동 
    if snake.get(x) :
        x = snake[x]
    # 1부터 6까지 주사위를 굴려 나온 수만큼 이동한 칸마다 방문 하지 않았으면 방문 표시하고 주사위 던진 횟수 +1 하여 큐에 삽입 
    for i in range(1,7):
      if x+i <= 100 and not visited[x+i]:
        visited[x+i] = True
        q.append((x+i, cnt + 1))
  
n, m = map(int,input().split())

ladder = dict()
snake = dict()

# 도착한 칸 key, 이동할 칸 value 
for _ in range(n):
  a, b = map(int,input().split())
  ladder[a] = b

for _ in range(m):
  a, b = map(int,input().split())
  snake[a] = b 

visited = [False] * 101

print(bfs(1))