[알고리즘][Python] 백준 16928 뱀과 사다리 게임 문제 풀이

문제 출처 : www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

---

문제 해석 : 주사위를 굴려서 1에서 100으로 이동하는데 걸리는 최소 주사위 굴리는 횟수를 구하는 문제이다.

 

문제 풀이 : heapq를 사용해서 BFS 형식으로 풀이할 수있다. 딕셔너리로 저장해 높은 사다리나 뱀인 경우에는 강제로 이동시키고, 그렇지 않을 경우 1~6칸을 이동시키면서 가장 먼저 100에 도달하는 경우에는 반복문을 빠져나온다.

 

풀이 시간 (기록용) : 40분

 

---

풀이 코드

from collections import defaultdict
import heapq

N, M = map(int, input().split())

move = defaultdict(int)

for _ in range(N):
    x, y = map(int, input().split())
    move[x] = y

for _ in range(M):
    x, y = map(int, input().split())
    move[x] = y

Q = []
heapq.heappush(Q, [0,1])
answer = 1e9
visited = [0] * 101
visited[1] = 1

while Q:
    now_count, now = heapq.heappop(Q)

    if now == 100:
        answer = min(now_count, answer)
        break
    for i in range(1,7):
        if now + i < 101:
            if visited[now+i] == 0:
                if now+i in move.keys():
                    heapq.heappush(Q, [now_count+1, move[now+i]])
                    visited[move[now+i]] = 1
                else:
                    heapq.heappush(Q, [now_count + 1, now + i])
                    visited[now+i] = 1
print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.