BOJ-16928 뱀과 사다리 게임

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

문제 소개

뱀과 사다리 게임은 주사위를 굴려 1번 칸에서 시작하여 100번 칸에 도착하는 게임이다.

주사위를 굴려 이동할 수 있는 거리는 1부터 6까지이며, 이동한 결과 칸에 사다리 또는 뱀이 있다면 각각이 가리키는 칸으로 이동해야 한다.

게임판의 상태가 주어졌을 때 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구한다.

문제 풀이

주어진 그래프 내에서 목적지까지의 최소 횟수를 찾는, 특정 칸에서 이동을 강제하는 요소가 추가된 BFS문제이다.

사다리와 뱀에 대한 정보는 시작점과 도착점이 주어지고 이동한다는 점에서 같다고 생각하였기 때문에 따로 구분하지 않고 jump라는 딕셔너리에 같이 저장해 두었다.

딕셔너리 cnt에는 각 칸까지 이동하기 위한 최소 횟수를 저장한다. 특정 칸까지 이동할 수 있는 방법이 여러가지가 있는 경우, 최소 횟수인 경우를 선택하기 위해서 선언하였다.

함수 bfs내에서 사용하는 큐인 queue에는 특정 칸까지 가기까지 주사위를 몇 번 굴렸는지를 튜플 형태로 삽입하게 된다.

예를 들어, (30, 3)은 30번 칸까지 주사위를 3번 굴려서 도달했음을 뜻한다.

이제 동작을 알아보면 아래와 같다.

1. queue에서 pop한 위치를 시작점으로 하여 주사위를 1 부터 6까지 굴렸을 때를 각각 생각해 본다.

2. 도착지가 100번 이하인 경우에 한하여 jump에 속하는지 검사한다.

   • jump에 속한다면 연속으로 jump에 속하는 동안 계속 이동시키며 위치값을 갱신한다.

   (예를 들어, 3에서 5로 가는 사다리와 5에서 8로 가는 사다리가 같이 존재한다고 생각해 보자)

3. 도착지가 이전까지 도달하지 않았던 곳이거나 또는 새로운 횟수가 기존 횟수보다 더 적다면 갱신한다.

코드

from sys import stdin
from collections import deque
input = lambda: stdin.readline().rstrip()


def bfs():
    queue = deque([(1, 0)])
    while queue:
        x, y = queue.popleft()
        # 100번 칸에 도달한 경우
        if x == 100:
            print(y)
            break

        # 주사위의 숫자는 1 부터 6까지
        for i in range(1, 7):
            target = x + i
            # 100보다 큰 칸은 없음
            if target <= 100:
                # jump가 가능한 동안 계속 위치를 갱신
                while target in jump:
                    target = jump[target]
                # 도달하지 않았던 곳이거나 새로운 횟수가 기존 횟수보다 더 적다면
                if target not in cnt or y + 1 < cnt[target]:
                    cnt[target] = y + 1
                    queue.append((target, y + 1))
                    

n, m = map(int, input().split())

jump = dict()
cnt = dict()

for _ in range(n + m):
    x, y = map(int, input().split())
    jump[x] = y
# 1번 칸은 0번으로 초기화
cnt[1] = 0

bfs()