[Baekjoon/Python] 16928번: 뱀과 사다리 게임(BFS)

# Baekjoon 16928번: 뱀과 사다리 게임

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
visited = [0 for _ in range(101)] 
ladder = [tuple(map(int, input().split())) for _ in range(N)]
snake = [tuple(map(int, input().split())) for _ in range(M)]
visited_ladder = [None for _ in range(101)]
visited_snake = [None for _ in range(101)]

for x, y in ladder:
    visited_ladder[x] = y

for u, v in snake:
    visited_snake[u] = v

res = 0
def BFS(m):
    
    queue = deque([])
    queue.append(m)
    visited[m] = 1
    
    while queue:
        pre = queue.popleft()
        
        if pre == 100: # 도착한 경우
            return visited[pre] - 1
        
        for i in range(1, 7):
            num = pre + i
            
            if num > 100:
                continue
            
            if visited_ladder[num]: # 사다리에 방문한 경우
                num = visited_ladder[num]
            
            if visited_snake[num]: # 뱀에 방문한 경우
                num = visited_snake[num]
                
            if visited[num] == 0: # 비어있는 경우
                visited[num] = visited[pre] + 1
                queue.append(num)
                
            
            
result = BFS(1)
print(result)

이 문제는 BFS 알고리즘 문제였다. 사다리와 뱀의 좌표를 저장하고, queue에서 추출한 원소를 기준으로 for문을 사용해 주사위의 범위에 속하는 index를 탐색한다.
해당 index가 100인 경우에는 도착한 지점이므로 return 후 종료한다.
해당 index가 뱀 혹은 사다리인 경우에는 뱀과 사다리 좌표를 저장한 list에서 값을 추출한다.
그렇게 해서 바뀐 index가 비어있는 경우에는 지금이 몇 번째로 주사위를 돌렸는지 visited 리스트에 저장하고, queue에 index를 추가한다.

위의 그림은 사다리가 2 72 / 6 80 / 8 52에 위치할 때의 BFS가 어떻게 작동되는지를 그림으로 나타낸 것이다.