Baekjoon 16928번 문제 - 뱀과 사다리 게임

Baekjoon 16928번 문제 - 뱀과 사다리 게임

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

이번에 살펴볼 문제는 고전 보드게임인 "뱀과 사다리 게임"을 구현해보는 것이다.

"뱀과 사다리 게임"은 시작지점에서 주사위를 굴려 나온 눈의 수만큼 말을 앞으로 이동시키며 도착지점에 먼저 다다르는 사람이 이기는 게임이다.

이 게임의 가장 중요한 룰은

사다리나 뱀을 만나면 이어진 칸으로 이동한다는 것!

사다리를 만나면 보통 먼거리를 한번에 앞지를 수 있고, 뱀을 만나면 다시 뒤로 멀리 보내질 수 있다.

이런 룰을 갖고 있는 게임을 구현하기 위해서는 어떻게 해야할까?

우선 나의 첫번째 아이디어는 다음과 같았다.

1. DP를 사용하면 괜찮을 것 같은데?

이전 포스팅에서 DP(다이나믹 프로그래밍, Dynamic Programming)에 대해 간단히 이야기를 했었다. (이를 다룬 예제는 아래를 확인하길!)

2021.10.20 - [algorithm problems] - Baekjoon 10844번 문제 - 쉬운 계단 수

다시 한번 설명하자면,

DP는 지정된 룰을 지키면서 한단계 한단계마다 최고의 효율을 낼 수 있는 경우를 생각하고, 최종 목적지에 도달하기까지 최소 횟수를 구하는 방법이다.

즉, 1부터 100까지 각 지점에 도달할 수 있는 최소 주사위 횟수를 구하고, 100에 저장되는 값을 출력하는 아이디어이다.

이를 구현한 코드는 다음과 같다.

주석에도 적어놓았지만, 이는 실패한 코드.

사다리와 뱀에 대한 정보를 받아오고, while 문을 활용하여 각 지점에 도달할 수 있는 최소 횟수를 move 리스트에 저장한다.

최종적으로 move[100]을 출력하는 방법이었다.

결론은 실패하였다..!

왜 실패했는지 고민을 해보니 dp를 활용하여 최소 횟수를 생각하다보니, 사다리나 뱀을 만났을 때 이동하지 않는 경우가 최소인 경우도 있었다.

이를 쉽게 설명해줄 반례는 다음과 같다.

1 1

13 99

7 1

위와 같이 데이터를 입력한다면 결과는 4가 나와야하지만, 내 코드로는 3이 나온다.

# 내 코드의 실행 과정

1. 1에서 7로 이동 (6만큼)

2. 7에서 13으로 이동하고 사다리를 이용해 99로 이동 (6만큼 + 사다리)

3. 99에서 100으로 이동 (1만큼)

하지만 실제로는 위와 같이 움직일 수 없다.

# 실제 뱀과 사다리 게임에서의 실행 과정

1. 1에서 6으로 이동 (5만큼)

2. 6에서 12로 이동 (6만큼)

3. 12에서 13으로 이동하고 사다리를 이용해 99로 이동(1만큼 + 사다리)

4. 99에서 100으로 이동 (1만큼)

위와 같이 이동하여야하는 이유는 "사다리와 뱀을 만나면 반드시 움직여야한다!" 라는 룰 때문이고, dp를 이용하면 이를 만족할 수 없다.

그렇다면 어떤 알고리즘을 다뤄야할까?

2. BFS, 너비 우선 탐색

"너비 우선 탐색"이라는 알고리즘을 들어보았는가?

"깊이 우선 탐색, DFS"와 함께 자주 사용되는 알고리즘으로 최솟값을 구해라! 라는 문제에 단골로 사용되는 알고리즘이다.

아래의 그림으로 쉽게 표현할 수 있다.

출처: https://velog.io/@vagabondms/DFS-vs-BFS

트리의 모양으로 BFS, DFS를 알아볼 수 있는 쉬운 그림이다.

기준이 되는 지점(부모)부터 연결이 되어있는 지점(자식)으로 거리를 늘려가며 차근차근 탐색하여 목표 지점까지의 최소 거리를 측정할 수 있는 알고리즘이다.

BFS, DFS를 사용하는 경우 가장 중요한 것이 바로 이전에 갔던 지점을 재방문 하지 않는 것이다.

만약 위의 트리에서 1과 2가 연결이 되어있다면 아래와 같은 순환이 생길 수 있다.

0 -> 1 -> 2 -> 0 -> 1 -> 2 -> ... 끝없는 순환에 빠진다!

그래서 반드시 visited = [False for _ in range(노드의 개수)] 같은 리스트를 활용하여 방문 여부를 체크해주어야한다.

이러한 BFS를 활용하고자 하는 아이디어는 다음과 같다.

1. 시작 위치에서 주사위를 던져 시작한다.

2. 사다리와 뱀을 고려하여 주사위를 한번 던져 갈 수 있는 곳들 리스트를 구한다.

3. 만약 해당 지점이 이전에 방문했다면 제외한다. (이미 방문했다면 더 최소 횟수로 해당 지점에 방문 가능하다는 뜻!)

4. 주사위를 던진 횟수를 증가시키고, 리스트의 각 지점에서 다시 주사위를 던져 갈 수 있는 경우를 구한다. (2,3,4 반복)

5. 만약 갈 수 있는 지점 중 도착지점이 포함된다면 탐색을 멈추고, 그때까지의 주사위를 던진 횟수를 출력한다.

이해하기 조금 어려울 수는 있으나, 쉬운 BFS 문제를 연습하다보면 쉽게 응용할 수 있을 것이며, 그리 어렵지 않다는 것을 알 수 있다!

어쨌든 BFS와 위의 아이디어를 활용한 정답 코드는 다음과 같다.

3. 최종 코드

from collections import deque N,M = list(map(int, input().split())) visited = [False for _ in range(101)] ladder = [[],[]] snake = [[],[]] for _ in range(N): start, end = list(map(int, input().split())) ladder[0].append(start) ladder[1].append(end) for _ in range(M): start, end = list(map(int, input().split())) snake[0].append(start) snake[1].append(end) q = deque([1]) def CheckSnake(i,snake): return snake[1][snake[0].index(i)] def CheckLadder(i,ladder): return ladder[1][ladder[0].index(i)] def FindNext(q,ladder, snake, visited): nextLst = deque() while q: now = q.popleft() visited[now] = True for next in range(now+1, now+7): if next == 100: return deque() if 0

코드가 좀 길지만 FindNext 함수와 메인 while 문을 해석하는데 중점을 두면 이해가 쉬울 것이다.

그리 어렵지 않다!!

from http://khlee98.tistory.com/19 by ccl(A) rewrite - 2021-11-10 17:26:44