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

문제 출처

문제 유형

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

해당 문제는 solved.ac 사이트 기준 골드 5 문제입니다.

1에서 출발해서 100에 도달할 때 까지 주사위를 굴려서 나온 숫자대로 이동합니다. 여기서 조건이 추가 되는데,

• N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으로 이동한다는 의미이다.

• M개의 줄에는 뱀의 정보를 의미하는 u, v (u > v)가 주어진다. u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다.

• 1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다. 항상 100번 칸에 도착할 수 있는 입력만 주어진다.

그렇게 주사위의 수에 해당하는 숫자대로 이동하거나, 사다리나 뱀을 이용해서 가장 빨리 100에 도달하는 경우의 수를 찾는 문제입니다. 최적의 루트를 찾는 문제이기 때문에 너비 우선 탐색(bfs)를 사용했습니다.

풀이 코드

from collections import deque

a, b = map(int, input().split())

// 방문 여부 및 횟수 저장
answer = [0 for _ in range(101)]
visited = [False for _ in range(101)]

// 사다리와 뱀
snake = [0 for _ in range(101)]
climb = [0 for _ in range(101)]

// 너비 우선 탐색 - dict()을 사용하는 방법도 있음
def bfs():
    queue = deque()
    queue.append(1)

    while True:
        num = queue.popleft()

		// 100이 나오면 종료
        if num == 100:
            print(answer[100])
            break

		// 주사위 수
        for x in range(1, 7):
            next = num + x
            if next <= 100 and not visited[next]:
                if climb[next] != 0:
                    next = climb[next]

                if snake[next] != 0:
                    next = snake[next]

                if not visited[next]:
                    visited[next] = True
                    answer[next] = answer[num] + 1
                    queue.append(next)

// 사다리 입력
for _ in range(a):
    x, y = map(int, input().split())
    climb[x] = y

// 뱀 입력
for _ in range(b):
    x, y = map(int, input().split())
    snake[x] = y

bfs()