[백준/Python] 16928 뱀과 사다리 게임

📌문제 탐색하기

• 각 면에 1부터 6까지 수가 하나씩 적혀있는 정육면체 주사위 사용
• 보드판의 크기는 10x10로, 총 100개의 칸으로 나누어져 있음
  • 보드판의 각 칸에 1부터 100까지 수가 하나씩 순서대로 적혀있음
•  플레이어는 주사위를 굴려 나온 수만큼 이동
  • i칸에 있을 때, 주사위를 굴려 4가 나오면 i+4번 칸으로 이동
  • 만약 100번 칸을 넘어간다면 이동할 수 없음
  • 도착한 칸이 사다리라면 사다리를 타고 위로 이동
  • 도착한 칸에 뱀이 있다면 뱀을 따라서 아래로 이동
• 게임의 목표는 1번 칸에서 시작해서 100번 칸에 도착하는 것
• 위 보드 게임에서 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값 구하기

입력

• 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15), 뱀의 수 M(1 ≤ M ≤ 15)
• 둘째 줄부터 N개의 줄에 사다리 정보 x, y (x < y)
  • x번 칸에 도착하면 y번 칸으로 이동한다는 의미
• 다음 M개의 줄에 사다리 정보 u, v (u > v)
  • u번 칸에 도착하면 v번 칸으로 이동한다는 의미
• 1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아님
• 모든 칸은 최대 하나의 사다리 또는 뱀을 가짐 두 가지 모두를 가지는 경우는 없음
• 항상 100번 칸에 도착할 수 있는 입력만 주어짐

출력

• 100번 칸에 도착하기 위해 굴려야 하는 주사위 횟수의 최솟값

풀이 방법 생각해보기

일종의 최소 거리를 구하는 문제로, bfs를 사용해서 문제를 풀이할 수 있다.

보드판의 각 칸을 정점, 각 칸에서 이동할 수 있는 다른 칸까지의 경로를 간선으로 간주한다. 이 때, 각 칸에서 다른 칸으로 이동하는 방법은 해당 칸의 번호에 1부터 6까지를 더한 번호의 칸으로 이동하거나, 뱀 혹은 사다리를 이용하는 방법이 있다. 

 

📌코드 설계하기

1. 사다리의 수 N과 뱀의 수 M을 입력받는다.
2. 특정 칸에서 뱀 혹은 사다리로 이동할 수 있는 다른 칸을 저장할 리스트 ways를 생성하여 모든 요소를 0으로 초기화한다.
3. 사다리와 뱀의 출발 칸, 도착 칸 번호를 입력받아 ways[출발 칸 번호]에 도착 칸 번호를 할당한다.
4. 각 칸에 도착했을 때 주사위를 굴린 횟수를 저장할 리스트 dice_cnts를 생성해 모든 요소를 100으로 초기화한다.
5. collections.deque를 사용해 빈 큐 q를 생성하고, 출발칸인 1을 삽입 후 dice_cnts[1]에 0을 할당한다.
6. q가 빌 때까지 아래 과정을 반복한다.
   1. q에서 맨 앞 요소 num을 꺼낸다.
   2. ways[num]이 0이 아니라면, next_num은 ways[num]이 된다. 이후 dice_cnts[next_num] > dice_cnts[num]이라면 dice_cnts[next_num]에 dice_cnts[num]을 할당하고 q에 ways[num]을 삽입한다.
   3. ways[num]이 0이라면, num에 1부터 6까지 각각 더한 값이 100을 넘지 않는다면 해당 값이 next_num이 된다. 이후 dice_cnts[next_num] > dice_cnts[num]+1이라면 dice_cnts[next_num]에 dice_cnts[num]+1을 할당하고 q에 next_num을 삽입한다.
7. dice_cnts[100]을 출력한다.

 

📌시도 회차 수정사항

처음에는 특정 칸에 도달하기 위한 주사위 횟수의 최솟값에 따라 다른 칸에 도달하기 위한 주사위 횟수의 최솟값이 영향을 받는다는 것 때문에 dp로 풀이할 수 있겠다고 생각했다. 하지만 이 문제에서 뱀의 경우 이전 칸으로 돌아가기 때문에, 단순히 현재 칸까지의 최소 횟수만으로 전체 문제에 대한 최적해를 구할 수가 없었다. 이러한 점 때문에 bfs로 풀이를 고치고 AC를 받았다. 

 

📌정답 코드

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

N, M = map(int, input().split())
ways = [0]*101
for _ in range(N+M):
    start, end = map(int, input().split())
    ways[start] = end

dice_cnts = [100]*101

q = deque([1])
dice_cnts[1] = 0

while q:
    num = q.popleft()
    if ways[num]:
        next_num = ways[num]
        if dice_cnts[next_num] > dice_cnts[num]:
            dice_cnts[next_num] = dice_cnts[num]
            q.append(next_num)
    else:
        for i in range(1,7):
            next_num = num + i
            if next_num <= 100 and dice_cnts[next_num] > dice_cnts[num]+1:
                dice_cnts[next_num] = dice_cnts[num]+1
                q.append(next_num)

print(dice_cnts[100])