[백준 16928번] 뱀과 사다리 게임(골드5) - 파이썬(Python)

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

16928번: 뱀과 사다리 게임

문제

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

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

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

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

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

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

 

 

---

 나는 이 문제를 너비 우선 탐색(BFS)로 풀었다. DFS로도 풀 수 있지 않을까?싶은 생각도 든다.

BFS라고 생각한 이유는 한 게임 내 주사위를 던지면 나올 수 있는 경우의 수는 현재 위치에서 1~6칸 움직이고, 이때의 움직임은 Level이 하나 증가한다고 볼 수 있었기 때문이다.

 이 문제에서 파이썬을 풀 때 힘들었던 점은 deque였다ㅠ 처음에는 현재위치와 이동 횟수를 담은 리스트들을 넣는 리스트를 정의하여 큐처럼 사용했다. 그러나, 그렇게 구현하니 시간초과가 나왔다. 

 

<< list사용 후 시간초과가 나온 코드 >>

import sys
input = sys.stdin.readline

moveNext = {}
n, m = map(int, input().split())
for _ in range(n + m):
    x, y = map(int, input().split())
    moveNext[x] = y

q = [[1, 0]]  # 현재 위치, 이동 횟수
visited = [0 for x in range(101)]
while q:
    cur = q[0][0]
    cnt = q[0][1]
    visited[cur] = 1
    del q[0]
    if cur == 100:
        print(cnt)
        break

    while moveNext.get(cur):
        cur = moveNext[cur]
    for i in range(1, 7):
        if cur + i <= 100 and visited[cur + i] == 0:
            q.append([cur + i, cnt + 1])

 

 알아보니 시간초과의 파이썬의 deque를 사용하지 않았기 때문이었다.

참고한 티스토리 글은 다음과 같다.

https://wellsw.tistory.com/122

[파이썬] 덱 vs 리스트 속도 차이? (deque vs list speed 차이)

위 글에서 덱은 double-linked-list 이지만, 리스트는 array 의 형태라고 한다.

그래서, 리스트의 마지막 원소를 삭제하는 것은 문제가 되진 않지만, 그 외 원소를 삭제할 경우에는 array의 메모리를 한 칸씩 앞으로 옮겨야하기 때문에 O(n) 만큼의 시간이 걸리는 것이다. 그러나, 덱에서 popleft() 를 사용한다면 첫 번째 원소를 O(1) 만큼 빠르게 삭제가 가능하다.

 

 즉, 첫 번째 요소만을 지속적으로 꺼내야하는 해당 문제에서는 deque를 사용하는 것이 시간초과를 없앨 수 있는 방법이다.

 

 

 

<< 전체 코드 >>

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

moveMap = {}
n, m = map(int, input().split())
for _ in range(n + m):
    x, y = map(int, input().split())
    moveMap[x] = y

visited = [False] * 101
q = deque([(1, 0)])  # 시간초과를 없앤 방법
visited[1] = True

while q:
    cur, cnt = q.popleft()
    if cur == 100:
        print(cnt)
        break
    if moveMap.get(cur):
        cur = moveMap[cur]
    for i in range(1, 7):
        if cur + i <= 100 and visited[cur + i] == 0:
            q.append([cur + i, cnt + 1])
            visited[cur + i] = 1