[Python] BOJ 16928 - 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

# BFS문제이다.

# 100번 칸에 도착하기 위해 주사위를 굴려야하는 횟수의 최솟값을 구하는 문제

 

1. N개의 사다리의 (시작점, 끝점)과 M개의 뱀의 (시작점, 끝점)을 각각 dictionary에 넣어준다.

 

2. bfs()를 수행하는데, 처음에 1번칸에서 시작하므로 q에 1을 넣고 시작한다.

   2-1. 현재 x번째 칸에서 k값을 더한 x+k가 다음칸이다.

   2-2. 다음 칸(next)에 사다리나 뱀이 존재한다면 next를 ladder[next]나 snake[next]로 바꿔준다.

   2-3. 둘 다 없고, visited[next]가 False이면 q에 next를 넣고 방문처리를 한 뒤,

         dist[next] = dist[x] + 1을 통해 주사위를 굴린 횟수를 1 더해준다.

 

3. 100번째 칸에 도착했을 때 주사위를 굴린 횟수인 dist[100]을 출력한다.

 

from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
dice = [1,2,3,4,5,6]
visited = [False] * 101
dist = [0] * 101
ladder, snake = dict(), dict()
for _ in range(N):
	s, e = map(int,input().split())
	ladder[s] = e
for _ in range(M):
	s, e = map(int,input().split())
	snake[s] = e

def bfs(i):
	q = deque()
	q.append(i)
	visited[i] = True
	while q:
		x = q.popleft()
		for k in dice:
			next = x + k
			if 1 <= next <= 100:
				if next in ladder:
					next = ladder[next]
				if next in snake:
					next = snake[next]
				if not visited[next]:
					q.append(next)
					visited[next] = True
					dist[next] = dist[x] + 1
			
bfs(1)
print(dist[100])