[Python] 백준 16928. 뱀과사다리게임 (BFS)

문제 링크

문제 풀이

• 1번 칸을 시작으로 bfs 탐색을 한다.
• 특정 칸 x를 탐색할 때, 그 칸에 사다리나 뱀이 있는 경우인지, 주사위를 돌릴 수 있는 칸이지 구분
  • 사다리나 뱀이 있는 경우
    • 다음 칸은 jump[x]
    • 다음 칸까지의 비용(cnt)이 예전에 기록한 비용(cost[jump[x])보다 적을 경우메 다음 칸(jump[x])을 탐색 (이미 방문한 경우에도 탐색 가능)
    • 그렇지 않은 경우, 다음 칸을 탐색하지 않고 그냥 넘어감
  • 주사위를 돌릴 수 있는 칸인 경우
    • 1~6의 수만큼 이동하는 경우를 모두 고려
    • 다음 칸이 범위 내이고, 현재 경로의 비용이 예전 경로의 비용보다 적을 경우에만
    • 다음 칸을 탐색/재탐색함

Point

• 이미 방문한 칸이어도 그 칸까지의 비용(=주사위 돌린 횟수)이 예전 경로의 비용보다 더 적은 경우 다시 탐색해야 한다.
  • 대부분의 bfs 문제들은 칸을 방문한 적이 있는 경우, 다시 탐색하지 않는다.
    그 이유는 이후 방문한 경우는 비용이 더 크기 때문에 다시 탐색할 필요가 없다.
    그러나 재탐색하지 않는 근본적인 이유는 다음 칸으로 넘어갈 때 비용이 무조건 커진다는 전제가 존재하기 때문이다.
  • 그러나 이 문제에서는 다음 칸으로 갈 때 비용이 무조건 커지지 않기 때문에 위와 같은 발상은 유효하지 않다. 여기선 사다리나 뱀을 이용하면 주사위를 돌리지 않기 때문에 비용이 커지지 않는다. 그래서 비록 이미 방문한 칸임에도 불구하고, 비용이 더 적은 경우 탐색을 다시 하도록 해야 한다.

코드

import sys
from collections import deque
from math import inf

input = sys.stdin.readline

def bfs():
    q = deque([[1, 0]])
    while q:
        x, cnt = q.popleft()    #x: 현재 칸 번호, cnt: 주사위 돌린 횟수
        if x in jump:   #사다리나 뱀이 있는 칸인 경우
            if cnt < cost[jump[x]]:    #만약 현재 경로의 비용이 예전 경로의 비용보다 적을 경우에만
                cost[jump[x]] = cnt    
                q.append([jump[x], cnt])    #다음 칸을 탐색 또는 재탐색(이미 방문한 경우에도 탐색 가능)
            continue # 주사위 돌리지 않고 넘어감
        for i in range(1, 7):   #주사위 돌리는 경우
            nx = x + i
            if nx <= 100 and cnt + 1 < cost[nx]:   #다음 칸이 1)범위 내이고 2)현재 경로의 비용이 예전 경로의 비용보다 적을 경우에만
                cost[nx] = cnt + 1
                q.append([nx, cnt + 1])     #다음 칸을 탐색 또는 재탐색(이미 방문한 경우에도 탐색 가능)

if __name__ == "__main__":
    N, M = map(int, input().split())
    ladder = dict([map(int, input().split()) for _ in range(N)])
    snake = dict([map(int, input().split()) for _ in range(M)])
    jump = ladder | snake   #ladder와 snake 딕셔너리를 합침
    cost = [inf for _ in range(101)]    #i번째 칸으로 이동하기까지 주사위 돌린 횟수

    bfs()

    print(cost[100])