[Python | 백준] 16928번: 뱀과 사다리 게임

문제 요약

• 보드 게임에서 플레이어는 주사위를 굴려 1번 칸에서 100번 칸까지 이동해야 한다.
• 사다리는 도착하면 더 높은 번호로 이동하고, 뱀은 더 낮은 번호로 이동하게 한다.
• 100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 구한다.

 

풀이

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

def snakes_and_ladders(N, M, ladders, snakes):
    board = list(range(101))  # 보드의 각 칸 초기화

    for start, end in ladders.items():
        board[start] = end  # 사다리 설정

    for start, end in snakes.items():
        board[start] = end  # 뱀 설정

    queue = deque([(1, 0)])  # 초기 위치 (1번 칸)와 주사위 횟수 (0회)
    visited = [False] * 101  # 방문 여부 체크
    visited[1] = True  # 1번 칸 방문 표시

    while queue:
        position, dice = queue.popleft()  # 현재 위치와 주사위 횟수

        if position == 100:
            return dice  # 100번 칸에 도착하면 주사위 횟수 반환

        for i in range(1, 7):  # 주사위는 1부터 6까지 가능
            next_pos = position + i
            if next_pos <= 100:  # 보드 범위 내인지 확인
                next_pos = board[next_pos]  # 사다리 또는 뱀에 의한 위치 변경
                if not visited[next_pos]:  # 방문하지 않은 칸이면
                    visited[next_pos] = True  # 방문 표시
                    queue.append((next_pos, dice + 1))  # 새로운 위치와 주사위 횟수 추가

# 입력 처리
N, M = map(int, input().split())
ladders = {}
for _ in range(N):
    x, y = map(int, input().split())
    ladders[x] = y
snakes = {}
for _ in range(M):
    u, v = map(int, input().split())
    snakes[u] = v

print(snakes_and_ladders(N, M, ladders, snakes))

 

풀이 과정

1. 보드 초기화:
   • 보드를 1부터 100까지의 칸으로 초기화
2. 사다리와 뱀 설정:
   • 입력된 사다리와 뱀 정보를 이용해 보드를 업데이트.
   • 예를 들어, 사다리의 시작 칸을 사다리의 끝 칸으로, 뱀의 시작 칸을 뱀의 끝 칸으로 설정.
3. BFS 탐색:
   • BFS를 사용해 최소 주사위 횟수를 구한다. BFS는 최단 경로를 찾는 데 효과적인 방법!
   • 큐에는 현재 위치와 주사위를 굴린 횟수를 저장
   • 현재 위치에서 주사위를 굴려 다음 위치로 이동. 이동한 위치가 사다리 또는 뱀의 시작 칸이라면, 사다리 끝이나 뱀의 끝으로 이동
   • 방문하지 않은 칸이면 방문 표시를 하고, 큐에 다음 위치와 주사위 횟수를 추가
   • 위치가 100번 칸에 도착하면, 주사위를 굴린 횟수를 반환

 

BFS 탐색의 장점

• BFS는 시작점에서 각 정점까지의 최단 거리를 찾는 데 적합하다.
• 큐를 사용해 현재 위치에서 가능한 모든 다음 위치를 탐색하고, 이를 반복하여 100번 칸에 도달할 때까지 계속한다.
• 방문 배열을 사용해 이미 방문한 칸을 다시 방문하지 않도록 하여 불필요한 계산을 줄인다.