[백준] 16928_뱀과 사다리 게임 (Python)

16928_뱀과 사다리 게임 (Python)

0. 출처

• 유형 : 그래프 탐색 (gold 5)
• 링크 : 16928번: 뱀과 사다리 게임

1. 기록

• 22/07/05 (화)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 정리 참고

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
사다리의 수 / 뱀의 수
3 7
32 62
42 68
12 98
95 13
97 25
93 37
79 27
75 19
49 47
67 17

- 예제 출력 1 -
3

(1) 5를 굴려 6으로 이동한다.
(2) 6을 굴려 12로 이동한다. 이 곳은 98로 이동하는 사다리가 있기 때문에, 98로 이동한다.
(3) 2를 굴려 100으로 이동한다.

- 예제 입력 2 -
사다리의 수 / 뱀의 수
4 9
8 52
6 80
26 42
2 72
51 19
39 11
37 29
81 3
59 5
79 23
53 7
43 33
77 21

- 예제 출력 2 -
5

(1) 5를 굴려 6으로 이동하고, 사다리를 이용해 80으로 이동한다.
(2) 6을 굴려 86으로
(3) 6을 또 굴려 92로
(4) 6을 또 굴려 98로 이동하고
(5) 2를 굴려 100으로 이동한다.

- 반례 1 -
2 1
7 94
8 94
55 54

- 출력 1 -
2

(3) 코드

import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()


# 사다리의 수, 뱀의 수
n, m = map(int, input().split())

# graph
graph = [[0 for _ in range(10)] for _ in range(10)]
visited = [[0 for _ in range(10)] for _ in range(10)]
cnt = [[0 for _ in range(10)] for _ in range(10)]

k = int(1)

for i in range(10):
    for j in range(10):
        graph[i][j] = k
        k = k + 1

# fixme -  사다리 (ladder) 딕셔너리와 뱀 (snake) 딕셔너리 정의
l = {}
s = {}

# fixme - 사다리 만들어주기
for _ in range(n):
    start, end = map(int, input().split())
    l[start] = end

# fixme - 뱀 만들어주기
for _ in range(m):
    start, end = map(int, input().split())
    s[start] = end


# fixme - 현재 위치마다 이동할 수 있는 범위를 체크해줍니다.
def can_move_range(x, y):
    if x <= 8:
        if y <= 3:
            d = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6]]

        elif y == 4:
            d = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [1, -4]]

        elif y == 5:
            d = [[0, 1], [0, 2], [0, 3], [0, 4], [1, -5], [1, -4]]

        elif y == 6:
            d = [[0, 1], [0, 2], [0, 3], [1, -6], [1, -5], [1, -4]]

        elif y == 7:
            d = [[0, 1], [0, 2], [1, -7], [1, -6], [1, -5], [1, -4]]

        elif y == 8:
            d = [[0, 1], [1, -8], [1, -7], [1, -6], [1, -5], [1, -4]]

        elif y == 9:
            d = [[1, -9], [1, -8], [1, -7], [1, -6], [1, -5], [1, -4]]

    elif x == 9:
        if y <= 3:
            d = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6]]

        elif y == 4:
            d = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5]]

        elif y == 5:
            d = [[0, 1], [0, 2], [0, 3], [0, 4]]

        elif y == 6:
            d = [[0, 1], [0, 2], [0, 3]]

        elif y == 7:
            d = [[0, 1], [0, 2]]

        elif y == 8:
            d = [[0, 1]]

        elif y == 9:
            d = [[0, 0]]

    return d


def roll_the_dice(sx, sy, cnt):
    q = deque([])
    q.append((sx, sy))

    while q:
        x, y = q.popleft()
        d = can_move_range(x, y)

        for i in range(len(d)):
            nx = x + d[i][0]
            ny = y + d[i][1]

            # fixme - 아직 방문하지 않았고
            if 0 <= nx <= 9 and 0 <= ny <= 9:
                if visited[nx][ny] != 1:

                    # fixme - 사다리 인 경우
                    if graph[nx][ny] in l.keys():
                        target = l[graph[nx][ny]]
                        for x1 in range(10):
                            for y1 in range(10):
                                if graph[x1][y1] == target and visited[x1][y1] != 1:
                                    q.append((x1, y1))
                                    visited[nx][ny] = 1
                                    visited[x1][y1] = 1
                                    cnt[x1][y1] = cnt[x][y] + 1

                    # fixme - 뱀인 경우
                    if graph[nx][ny] in s.keys():
                        target = s[graph[nx][ny]]
                        for x1 in range(10):
                            for y1 in range(10):
                                if graph[x1][y1] == target and visited[x1][y1] != 1:
                                    q.append((x1, y1))
                                    visited[nx][ny] = 1
                                    visited[x1][y1] = 1
                                    cnt[x1][y1] = cnt[x][y] + 1

                    # fixme - 그냥 칸만 있는 경우
                    else:
                        q.append((nx, ny))
                        visited[nx][ny] = 1
                        cnt[nx][ny] = cnt[x][y] + 1

    return cnt


cnt = roll_the_dice(0, 0, cnt)
print(cnt[9][9])

(4) 정리

그림1

'그림1'과 같은 경우 노란색 사다리를 타면 도착지점에 빨리 갈 수 있는 것처럼 보이지만 사실상 파란색 사다리를 타야 도착지점에 도달할 수 있습니다. 따라서 현재위치와 가까운 사타리를 타고 내려가는게 아닌 모든 칸에 대해서 몇번의 주사위를 굴려야 도착할 수 있는지 완전탐색해주어야 합니다.

 

그림2

풀이의 대부분이 1차원 배열로 구현해서 풀었습니다. 저는 처음에 2차원 배열로 구상하고 풀었기 때문에 j <= 3 열이 3이하인 경우 해당 행에서 6칸을 이어서 나아갈 수 있지만 i == 4 인 경우부터 i == 9 인 경우까지는 주사위를 굴릴시 열이 바뀌는 경우가 생깁니다. 해당 경우를 모두 고려하여 코드로 작성해주었습니다.
또한 i == 9 이면서 j >= 4 인 경우에는 더 이상 나아갈 수 있는 칸이 없어 해당 경우도 따로 elif 문으로 빼주었습니다.
해당 문제는 1차원 배열로 구현해서 푸는게 훨씬 쉽게 풀 수 있을거라 생각됩니다.

 

(5) 참고