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

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

 

BFS 문제였다.

queue에 주사위를 한 번 던질 때 갈 수 있는 모든 칸을 queue에 저장하고 만약 만약 queue에 100이 들어오면 while문을 멈춘다.

from collections import deque
n,m = map(int,input().split())

# 사다리
ladder = dict()
for i in range(n):
    x,y = map(int,input().split())
    ladder[x] = y

#뱀
snake = dict()
for i in range(m):
    x,y = map(int,input().split())
    snake[x] = y

#방문 리스트
graph = [0] * 101

queue = deque([1])
cnt = 0
flag = True
while flag:
    length = len(queue)
    for _ in range(length):
        x = queue.popleft()

        # 100번째 칸으로 이동한 경우
        if x == 100:
            print(cnt)
            flag = False
            break
        
        # 주사위 1 ~ 6 까지 돌리기
        for i in range(1,7):
            nx = x + i

            # 100번째 칸을 넘어가지 않고 방문하지 않았던 칸이라면
            if nx <= 100 and graph[nx] == 0:
                graph[nx] = 1

                #사다리 칸인지 확인
                if nx in ladder.keys():
                    graph[ladder[nx]] = 1
                    queue.append(ladder[nx])
                
                #뱀 칸인 경우
                if nx in snake.keys():
                    graph[snake[nx]] = 1
                    queue.append(snake[nx])

                #둘 다 아닐 경우는 그냥 이동
                else:
                    queue.append(nx)
    # 100번째 칸으로 이동하지 못했으면 cnt+1
    cnt += 1