[BOJ] #16928 뱀과 사다리 게임 (Python)Snake and Ladder Game (Python)
📅
🚀
알고리즘 분류 🔗
그래프 이론, 그래프 탐색, 너비 우선 탐색(BFS)
🚀
문제 설명 🔗
전형적인 뱀과 사다리 게임을 구현하는 문제입니다. 100개의 칸이 있는 보드에서 주사위를 굴려서 이동합니다. 주사위는 1부터 6까지의 숫자가 나올 수 있습니다.
게임의 목표는 1번 칸에서 100번 칸으로 갈 때, 최소 몇 번의 주사위를 굴려야 하는지를 구하는 것입니다.
뱀과 사다리 게임
✅
입력 🔗
- 첫째 줄에 사다리의 개수 N (1 ≤ N ≤ 15)과 뱀의 개수 M (1 ≤ M ≤ 15)이 주어집니다.
- 둘째 줄부터 N + 1번째 줄까지 사다리의 시작과 끝 위치가 주어집니다. (1 ≤ 시작 < 끝 ≤ 100)
- N + 2번째 줄부터 N + M + 1번째 줄까지 뱀의 시작과 끝 위치가 주어집니다. (1 ≤ 시작 < 끝 ≤ 100)
✅
출력 🔗
- 1번 칸에서 100번 칸으로 가기 위해 필요한 최소 주사위 굴리기 횟수를 출력합니다.
🚀
풀이 🔗
- 뱀, 사다리의 시작 위치를 key로, 끝 위치를 value로 하는 딕셔너리를 만듭니다.
- 100개의 칸을 가진 1차원 배열에 각 칸의 최소 주사위 굴리기 횟수를 저장합니다. 기본값은 99로 설정합니다.
- 1번 칸에서부터 (1부터 6까지) 주사위를 굴려서 이동할 수 있는 칸에 이전 칸의 주사위 굴리기 횟수 + 1을 저장합니다.
- 만약 해당 칸이 업데이트된다면, 큐에 해당 칸을 추가합니다.
- 다시 큐에서 꺼낸 칸에 대해 1부터 6까지의 주사위를 굴려서 이동 가능한 칸을 확인합니다.
- 이 과정을 반복하여 큐에 남아있는 칸이 없을 때까지 진행합니다.
- 마지막 칸(100번 칸)의 주사위 굴리기 횟수를 출력합니다.
🚀
코드 - Python 🔗
import sys
from collections import deque
N, M = list(map(int, sys.stdin.readline().split()))
arr = [99] * 101 # 1부터 100까지의 칸을 저장하는 배열, 기본값은 99로 설정
snakes = {} # 사다리와 뱀의 위치를 저장하는 딕셔너리
for _ in range(N + M):
a, b = list(map(int, sys.stdin.readline().split()))
snakes[a] = b # 사다리와 뱀의 시작 위치를 key로, 끝 위치를 value로 저장
arr[1] = 0
dq = deque([1]) # 큐에 1번 칸을 추가
while dq:
x = dq.pop() # 큐에서 꺼낸 칸
for i in range(1, 7): # 1부터 6까지의 주사위를 굴려서 이동할 수 있는 칸을 확인
if x + i > 100: # 100번 칸을 넘어가면 무시
continue
elif x + i in snakes.keys(): # 사다리와 뱀의 위치를 확인
if arr[x] + 1 < arr[snakes[x+i]]: # 값이 업데이트되는 경우
arr[snakes[x+i]] = arr[x] + 1
dq.append(snakes[x+i]) # 업데이트된 칸을 큐에 추가
else: # 사다리와 뱀의 위치가 아닌 경우
if arr[x] + 1 < arr[x + i]: # 값이 업데이트되는 경우
arr[x + i] = arr[x] + 1
dq.append(x + i) # 업데이트된 칸을 큐에 추가
print(arr[-1]) # 마지막 칸(100번 칸)의 주사위 굴리기 횟수를 출력🚀
핵심 🔗
- BFS를 사용하여 1번 칸에서 100번 칸으로 가는 최단 경로를 찾습니다.
- 사다리와 뱀의 위치를 딕셔너리로 관리하여 이동할 수 있는 칸을 쉽게 확인합니다.
- 큐를 사용하여 BFS를 구현합니다.
🚀
반례 모음(예제 제외) 🔗
2 1
2 60
21 99
61 201 5
2 99
3 2
4 2
5 2
6 2
7 20 01 5
2 92
94 3
95 4
96 5
97 6
98 71 1
13 99
8 7