문제 링크: https://www.acmicpc.net/problem/16928

Thumbnail: Photo by VD Photography (Unsplash)

다들 한번쯤은 들어보셨을 법한 클래식한 보드게임 입니다!

풀이

​DFS로 풀이할 수 있습니다.

풀이에 앞서, 먼저 뱀과 사다리 게임의 규칙을 간단하게 정리해 봅시다.

• 시작점은 1, 도착점은 100인 100칸짜리 보드판에서 게임을 진행한다.
• 1~6의 값을 가지는 정육면체 주사위 1개를 굴려 이동합니다.
• 만약 도착한 칸에 뱀이나 사다리가 있다면, 무조건 이용해야 합니다.
• 만약 주사위를 굴려 나온 숫자만큼 이동했을 때, 결과가 100을 넘어간다면 이동할 수 없다.

문제에서 입력으로 사다리와 뱀의 위치 정보를 제공합니다. 주사위의 눈은 항상 원하는 수가 나온다고 가정할 때, 주사위를 최소한으로 굴려서 도착점에 도달하려면 최소 몇 번 굴려야 하는지 계산하는 문제입니다.

허나, 이 풀이의 경우 반복 횟수로 인해 시간 초과가 발생합니다. 따라서, 시간 안에 동작하도록 반복 횟수를 줄여야 합니다. 그렇다면, 고려하지 않아도 되는 경우는 반복하지 않게끔 개선해봅시다.

입력 처리

사다리와 뱀에 대한 정보는 모두 (출발점, 도착점) 의 형태로 입력됩니다. 굳이 각각을 배열을 나눠서 판단할 필요는 없으니, 하나의 배열에 사다리와 뱀의 정보를 모두 저장했습니다.

길이 101짜리 roads 배열(1~100의 인덱스를 사용하기 위함) 을 만들고, 사다리와 뱀의 출발점에 해당하는 자리에 도착점을 값으로 저장했습니다.

• 배열의 값이 0이 아니라면 그 위치에 뱀 또는 사다리가 존재합니다.
• idx에 있는 뱀 또는 사다리로 이동하게 되는 도착점은 roads[idx] 입니다.

roads = [0 for _ in range(101)]
for _ in range(N + M):
    start, end = map(int, input().split())
    roads[start] = end

DFS - 너비 우선 탐색

​​이제 보드판을 탐색하면서 도착점을 향해 이동해 봅시다. 기본적인 원리는 DFS와 동일하게, 현재 노드를 탐색하면서 다음에 방문할 노드를 미리 큐에 넣어두는 방식을 사용합니다.

길이 101짜리 board 배열(1~100의 인덱스를 사용하기 위함) 을 만들고, 0으로 초기화합니다.

• 배열의 원소가 0이라면, 아직 방문하지 않은 위치입니다.
• 0이 아니라면, 현재 위치까지 도달하는 데 사용한 주사위의 개수입니다.
• 다음 위치를 큐에 넣을 때, 아래의 조건을 확인해야 합니다.
  • 만약 현재 위치 + 주사위의 눈 이 100을 넘는다면, 이동할 수 없으니 큐에 포함할 수 없습니다.
  • 만약 다음에 이동할 위치에 뱀 또는 사다리가 있다면 (roads 배열로 확인) 무조건 이용해야 합니다.

from collections import deque   # 꼭 Double-ended queue가 아니라 Queue형태면 다 됩니다.

board = [0 for _ in range(101)] # 방문 여부는 배열의 값이 0이 아닌지로 판단한다.
queue = deque([1])
while queue:
    current = queue.popleft()
    if current == 100:
        print(board[current])
        break
    for i in range(1, 7):       # 1~6까지 주사위를 굴려서 각 경우를 계산한다.
        next = current + i
        if next > 100:          # 규칙: 100을 넘어가면 이동할 수 없다.
            continue
        if roads[next] != 0:    # 규칙: 사다리 또는 뱀을 만나면 무조건 이용해야 한다.
            next = roads[next]
        if board[next] == 0:    # 중복 방문을 방지한다.
            board[next] = board[current] + 1
            queue.append(next)

전체 코드

from collections import deque
input = open(0).readline

N, M = map(int, input().split())
board = [0 for _ in range(101)]    # 방문 여부는 배열의 값이 0이 아닌지로 판단한다.
roads = [0 for _ in range(101)]
for _ in range(N + M):
    start, end = map(int, input().split())
    roads[start] = end

queue = deque([1])
while queue:
    current = queue.popleft()
    if current == 100:
        print(board[current])
        break
    for i in range(1, 7):       # 1~6까지 주사위를 굴려서 각 경우를 계산한다.
        next = current + i
        if next > 100:          # 규칙: 100을 넘어가면 이동할 수 없다.
            continue
        if roads[next] != 0:    # 규칙: 사다리 또는 뱀을 만나면 무조건 이용해야 한다.
            next = roads[next]
        if board[next] == 0:    # 중복 방문을 방지한다.
            board[next] = board[current] + 1
            queue.append(next)