[Python] 백준/BOJ 16928번: 뱀과 사다리 게임 (Gold 5)

💻 Problem

문제 보러 가기

 

게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.

플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다. 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다. 즉, 사다리를 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 크고, 뱀을 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 작아진다.

게임의 목표는 1번 칸에서 시작해서 100번 칸에 도착하는 것이다.

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

 

💡 Approach

어렸을 때 좋아했던 게임이다.......🥹

다들 이 게임을 아시나요.. 어렸을 때 정말 재밌게 했었는데........

저기 보면 오른쪽 아래에 있는 게임이 뱀과 사다리 게임 ㅠㅠㅠㅠ 뿡뿡이에선 뱀이 아니라 파이프였다..!!

 

내 추억 ㅠ 아무튼!!

게임판은 총 100개의 칸으로 나누어져 있는 10×10 보드판이다.

10×10 보드판이지만 상하좌우로 이동하는 것이 아니라 1부터 100까지의 칸 중 주사위를 굴려 다음 칸으로만 이동하기 때문에 2차원 배열이 아니라 1차원 배열이다.

 

먼저 보드판에 1부터 100까지의 칸을 만든다.

그 후 사다리의 정보와 뱀 정보를 입력받아 보드판을 갱신한다.

보드판의 index는 몇 번째 칸인지를 나타내고 value는 해당 칸의 이동 정보를 나타낸다.

• 만약, 3번째 칸에 뱀이나 사다리가 없다면 board[3]은 그대로 3일 것이다.
• 만약, 입력받은 사다리 정보가 10, 20일 때, 10번째 칸에 사다리가 있으니 board[10]은 20이다.
• 만약, 입력받은 뱀 정보가 40, 30일 때, 40번째 칸에 뱀이 있으니 board[40]은 30이다.

 

자, 보드판이 준비되었으니 이제 게임을 시작하자!

 

여기서부턴 우리가 잘 아는 bfs 코드이다.

이 루트에서 여태까지 주사위를 굴린 총횟수가 필요하니 큐에 위치를 넣을 때 주사위 굴린 횟수도 함께 넣어주자.

 

다음 위치는 주사위를 굴려 나온 숫자를 더한 위치이다.

주사위는 1부터 6 사이로 나올 수 있으니 6번의 반복문을 통해 탐색하면 된다.

 

이미 사전에 보드판에 사다리와 뱀 정보를 기록해두었으니 board[다음 위치]를 하면 사다리나 뱀이 없는 칸이면 다음 위치 그대로 있을 것이고, 사다리나 뱀이 있는 칸이면 그것을 타고 이동한 위치를 큐에 넣을 것이다.

 

✏️ Solution

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

def game_start():
    queue = deque([(1, 0)])

    while queue:
        pos, cnt = queue.popleft() # 현재 위치, 주사위 굴린 횟수

        # 100번 칸에 도착하면 종료한다
        if pos == 100:
            return cnt

        # 주사위를 1부터 6 사이로 굴린다
        for i in range(1, 7):
            npos = pos + i # 다음 위치

            # 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다
            if npos > 100:
                break

            # 이미 방문한 곳이면 탐색하지 않는다
            if visited[npos]:
                continue

            # 다음 위치를 방문 처리한다
            visited[npos] = True
            # 다음 위치가 사다리랑 뱀 모두 아니면 주사위 칸만큼 이동하고
            # 다음 위치가 사다리거나 뱀이면 타고 이동한다
            queue.append((board[npos], cnt + 1))

n, m = map(int, input().split()) # 사다리의 수, 뱀의 수
board = [i for i in range(101)] # 게임맵 (현재 숫자 칸 번호)
visited = [False] * 101

# 사다리 정보 + 뱀 정보 기록
for _ in range(n + m):
    # x번 칸에 도착하면, y번 칸으로 이동
    x, y = map(int, input().split())
    # 사다리나 뱀의 도착 좌표로 갱신한다
    board[x] = y

print(game_start())

시간은 100 + 15 + 15로 매우 짧다!