Python으로 뱀과 사다리 게임의 최소 주사위 굴림 횟수 찾기

문제 개요

뱀과 사다리(Snakes and Ladders) 게임을 하고 있다고 가정해 보겠습니다. 이 게임에는 특별한 조건이 있는데, 주사위에서 원하는 숫자를 자유롭게 선택할 수 있다는 것입니다. 시작 위치는 0이고 목표 지점은 100번 칸이며, 목표에 도달할 때까지 주사위를 여러 번 굴립니다.

보드 위에 배치된 뱀과 사다리의 위치 정보가 주어질 때, 목표 지점에 도달하기 위해 필요한 최소 주사위 굴림 횟수를 구해야 합니다. 배열 snakes와 ladders는 보드 위 뱀과 사다리의 위치를 나타내며, 각 항목은 해당 뱀 또는 사다리의 시작 칸과 끝 칸 값을 담고 있습니다.

예를 들어 입력이 다음과 같다면,

ladders = [(11, 40), (37, 67), (47, 73), (15, 72)]
snakes = [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]

출력은 8이 됩니다. 즉, 주어진 뱀과 사다리 배치에서 100번 칸까지 도달하는 데 필요한 최소 이동 횟수는 8번입니다.

해결 전략: 너비 우선 탐색(BFS)

각 주사위 굴림을 그래프의 한 단계(level)로 생각하면, 이 문제는 시작점에서 목표점까지의 최단 경로를 찾는 문제로 변환됩니다. 따라서 BFS(너비 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 구체적인 절차는 다음과 같습니다.

배열 snakes를 배열 ladders에 추가하여 하나의 이동 규칙 리스트로 통합합니다.
edges라는 새로운 딕셔너리(맵)를 생성합니다.
통합된 리스트의 각 쌍 (f, t)에 대해 edges[f] = t로 설정합니다. 이는 f번 칸에 도착하면 t번 칸으로 이동함을 의미합니다.
u: 이미 방문한 칸을 저장하는 집합(set)입니다.
v: 현재 단계에서 탐색 중인 칸을 저장하는 집합입니다. 초기값으로 1을 추가합니다.
m: 주사위 굴림 횟수 카운터로 0으로 초기화합니다.
v에 100이 포함되지 않은 동안 아래 과정을 반복합니다:
- m을 1 증가시킵니다.
- 새로운 집합 w를 생성합니다.
- v의 각 위치 f에 대해, 주사위 눈금 i(1~6)마다:
  - n = f + i를 계산합니다.
  - n이 edges에 존재하면, n을 edges[n](뱀이나 사다리의 끝 칸)으로 갱신합니다.
  - n이 이미 방문 집합 u에 있으면 건너뜁니다.
  - 그렇지 않으면 n을 u와 w에 추가합니다.
- v = w로 갱신하여 다음 단계로 진행합니다.
반복이 종료되면 m(최소 굴림 횟수)을 반환합니다.

구현 예제

아래 파이썬 코드를 통해 실제 동작을 확인해 보겠습니다.

def solve(ladders, snakes):
    ladders.extend(snakes)
    edges = {}
    for f, t in ladders:
        edges[f] = t

    u = set()
    v = set()
    v.add(1)
    m = 0
    while 100 not in v:
        m += 1
        w = set()
        for f in v:
            for i in range(1, 7):
                n = f + i
                if n in edges:
                    n = edges[n]
                if n in u:
                    continue
                u.add(n)
                w.add(n)
        v = w
    return m

print(solve([(11, 40), (37, 67), (47, 73), (15, 72)],
            [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]))

입력

[(11, 40), (37, 67), (47, 73), (15, 72)], [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]

출력

동작 원리 정리

이 알고리즘은 한 번의 주사위 굴림으로 도달 가능한 모든 칸을 레벨별로 확장해 나갑니다. 뱀을 만나면 아래로 내려가고, 사다리를 만나면 위로 올라가는 이동이 edges 딕셔너리를 통해 자동으로 처리됩니다. 이미 방문한 칸은 집합 u로 관리하여 중복 탐색을 방지하므로, 100번 칸이 처음 등장하는 시점의 굴림 횟수가 곧 최솟값이 됩니다. BFS의 특성상 각 레벨이 곧 하나의 주사위 굴림에 해당하기 때문에, 처음 목표에 도달한 순간의 카운트가 정답임을 보장할 수 있습니다.