[골드 5] 16928번: 뱀과 사다리 게임

Original Source: https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

---

문제

뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다.

주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?

게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.

플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다. 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다. 즉, 사다리를 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 크고, 뱀을 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 작아진다.

게임의 목표는 1번 칸에서 시작해서 100번 칸에 도착하는 것이다.

게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해보자.

입력

첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다.

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

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

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

출력

100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 출력한다.

---

사고의 흐름

• 뱀은 무조건 피해야 한다. 칸 수가 줄어들어서 이득을 볼 일은 전혀 없으니까.
• 사다리는 무조건 타야 할까? 사다리가 4 → 5 로 놓여 있어도 6이 나오면 더 멀리 갈 수 있으니 이런 경우는 배제하는 게 맞아 보이는데.
• 일단 극단적인 케이스는 뒤로 제쳐두고 일반적인 해법을 생각해보자.
• 기본적으로는 주사위를 한 번 던졌을 때 플레이어가 움직일 수 있는 1칸 ~ 6칸 내에서 가장 멀리 이동할 수 있는 칸을 찾으면 된다.
• 그런데 문제는 주사위를 한 번만 던진다면 지금 한 번의 시행(==주사위 던짐)만을 고려하면 되겠지만, 두 번 이상 던질 때는 첫 번째 던졌을 때 최선의 선택을 함으로써 오히려 두 번째까지 던졌을 때 나올 수 있는 더 좋은 경우를 놓쳐버릴 수 있다. (ex. 사다리가 4 50 / 9 99 인 경우)
• 즉 그리디는 아니다? 이런 의미인가?
• 결국 플레이어가 100까지 이동했을 때 어느 경로가 최적의 경로인지는 전부 '가 봐야' 아는 셈이다.
• 그럼 탐색 중에 DFS가 맞을까, BFS가 맞을까?
• BFS가 맞는다. DFS는 기준에 따라 가장 깊숙한 노드까지 탐색하는 알고리즘이다. 예를 들면 '우선 가장 큰 6만 계속 던져 보자'라고 기준을 세워서 6 12 18 24 ... 이렇게 100까지 탐색한다. 반면 BFS는 인접한 노드들을 우선적으로 탐색하기 때문에 첫 번째 시행에 주사위 1, 2, 3, 4, 5, 6 을 모두 탐색하고, 두 번째 시행에서는 첫 번째 시행으로 도달한 플레이어의 위치를 기준으로 다시 주사위 1, 2, 3, 4, 5, 6 을 모두 탐색한다. 이런 식으로 계속 탐색하다가 100에 도달하는 경우가 최초로 등장했을 때 즉시 알고리즘을 종료하고 결과값을 출력해주면 된다.
• 그래프에 인접 노드(칸)들을 저장할 때, 사다리나 뱀이 없으면 현재 칸으로부터 1, 2, 3, 4, 5, 6만큼 떨어진 칸들을 저장해주면 된다. 예를 들어 현재 플레이어의 위치가 50이라면 그래프의 50번째 노드에 51, 52, 53, 54, 55, 56 을 저장하면 된다.
• 만약 사다리나 뱀이 있다면 플레이어가 이동하게 되는 위치를 저장해주면 된다. 예를 들어 현재 플레이어의 위치가 50인데 54 → 28 뱀이 있다면 50번째 노드에 저장되는 값은 51, 52, 53, 28, 55, 56 인 것이다.
• 이렇게 한 뒤 위에서 말했듯이 BFS를 실행해서 플레이어가 100에 도달하는 순간 종료하고 시행 횟수를 출력해주면 된다.

 

• 그래프를 초기화할 때 인접 노드의 값이 100이 넘어가면 append되지 않도록 자동으로 처리하고 싶은데, 어떻게 할 수 있는 방법이 없을까?
• 각 인접 노드를 i+1, i+2, i+3, ... 이런 식으로 하드코딩하지 말고, for문을 한번 더 돌리면서 if문을 붙여서 100이 넘어가면 원소로 포함되지 않도록 하면 되지 않을까? → 되네!
• 100번째 칸에 도달하는 순간 알고리즘이 더 이상 실행되지 않으니 100번째 칸의 인접 노드는 필요 없겠다.

 

• 그런데 내가 푸는 방법대로 풀면 굳이 BFS를 사용할 없이 재귀 함수로만 풀어도 되지 않을까?
• 아...재귀 함수를 쓰면 Maximum Recursion Depth가 초과되네.
• 내가 잘못 생각했다. 각 시행별로 함수를 6번 동시에 실행시켜야 하는데, 재귀 함수로 실행시키면 첫 번째 인접 노드만을 계속 타고 들어가니까 다른 인접 노드들이 고려되지 않는다. 그래서 BFS를 써야 하는구나.

 

• 시행별로 탐색을 6번 실행하면 최악의 경우 6^17의 경우를 모두 고려해야 한다. 이건 좀...
• 그럼 인접 노드에 사다리가 있다면 사다리와 6(최댓값)에 대해서만 탐색을 수행하고, 사다리가 없으면 무조건 6에 대해서만 탐색을 수행하면 고려해야 하는 경우의 수를 크게 줄일 수 있겠다.
• 만약 주사위 눈이 6이 나왔을 때 도착지에 사다리가 있다면? 그 도착 지점의 사다리 너머도 탐색을 해줘야 한다. 왜냐하면 더 먼 칸까지 이동할 수 있는 사다리가 이후에 나올 수도 있으니까. 그럼 반복문을 하나 더 돌려서 '사다리가 존재하지 않는, 주사위를 한 번 던져 이동할 수 있는 최대한 멀리 떨어진 지점'을 찾아야겠다.
• 그리고 사다리가 있는 노드(칸)에 방문 처리를 해 놓아서 다음 탐색 시에 중복해서 사다리를 타지 않도록 해야겠다.

 

• 겨우겨우 구현을 해서 제출해봤는데 바로 틀렸다길래 반례를 찾아보니 뱀을 타고 가는 게 더 빠른 경우가 있다고 한다. 맞네...
• 이제 더는 못 풀겠다. 포기하자.

남이 작성한 소스코드

yunakim2 님:
https://yunaaaas.tistory.com/84

피드백

• 재귀 함수를 한 번에 여러 개 호출하면 맨 위의 함수만 계속 호출된다. 어찌 보면 당연한 건데 헷갈리기 쉬워 보인다.
• 한 번에 가장 일반적인 코드를 짜려고 하지 말고, 구체적인 한두 개의 케이스를 고려하며 짠 후 천천히 일반화의 정도를 올릴 것.
• 카운트를 정수형 변수에 저장해서 세지 말고, 모든 칸에 대응되는 리스트를 하나 만들어서 어떤 칸에 도달했을 때 그 칸에 해당하는 인덱스에 카운트를 저장하는 게 편하다. 그렇게 해서 100번째 칸에 카운트가 입력되면 답으로 출력해주면 된다.
• 큐에 현재 칸 위치만 저장하지 않고, 현재 칸과 카운트를 한 쌍으로 만들어 저장하면 각각의 경우별로 카운트를 구분해서 사용할 수 있다. 그렇게 하면 반복문을 돌 때마다 카운트를 따로 처리할 필요 없이 1씩만 더해주면 된다.

---

재도전

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


# debug
def print_board(li):
    for i in range(0, 10):
        for j in range(10 * i, 10 * i + 10):
            print(li[j], end = " ")
        print()
    print(li[100])

    print("---------------------------------")

def bfs(dist, move_to):
    q = deque()
    q.append((1, 0))
    dist[1] = 0

    while q:
        cur_pos = q[0][0]
        cur_moves = q[0][1]     
        q.popleft()

        if cur_pos == 100:
            print(cur_moves)
            return

        for i in range(1, 7):
            if cur_pos + i > 100:
                continue
            
            if dist[cur_pos + i] != -1:
                continue

            dist[cur_pos + i] = cur_moves + 1

            is_ladder_or_snake = False
            for (v, w) in move_to:
                if cur_pos + i == v:
                    is_ladder_or_snake = True
                    q.append((w, dist[cur_pos + i]))

            if is_ladder_or_snake == False:
                q.append((cur_pos + i, dist[cur_pos + i]))
  

dist = [-1] * 101
move_to = []
n, m = map(int, r().split())
for _ in range(n+m):
    start, end = map(int, r().split())
    move_to.append((start, end))

bfs(dist, move_to)