[백준 파이썬] 16928 뱀과 사다리 게임

📌문제 출처

백준 단계별 문제풀이 - 그래프와 순회
https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

❓ 문제

 

 

❗ 풀이

• heap 자료구조 활용 bfs

📗 풀이 코드

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

def bfs():
    heap = [[0,1]] # 0회 이동, 출발점은 1번
    while heap :
        cnt, tmp = heappop(heap) # 현 위치, 이동 횟수
        cnt += 1 # 이동 횟수 증가
        for i in range(1,7): # 주사위 굴리기
            if tmp+i <= 100 : # 이동 가능하다면
                new = mov[tmp+i] # 새로운 곳으로 이동
                if visited[new] > cnt : # 현재 기록된 최소 방문 횟수보다 작다면
                    visited[new] = cnt # 최소 방문 횟수 초기화
                    if new == 100 : # 도착 했다면
                        return cnt
                    heap.append([cnt,new]) # 새롭게 이동
n,m = map(int,input().split())
mov,visited = {},{} # 이동하는 칸(뱀,사다리), 해당 칸 최소 방문 횟수
for i in range(1,101):
    mov[i], visited[i] = i,100 # 100번째 칸까지 최대 이동 횟수는 99이므로
for _ in range(n+m):
    sta,end = map(int,input().split())
    mov[sta] = end
print(bfs())

📗 코드 해설

• 해당 칸(key)에 도착했을 때 이동하는 칸(value)을 넣어놓은 mov라는 dictionary를 만든다.
  우선 뱀과 사다리가 없을 경우에는 해당 칸에서 머물러 있기에 key와 value가 똑같지만
  각 뱀과 사다리의 머리(key):꼬리(value)로 dictionary를 수정한다.
• visited라는 dictionary는 해당 칸에 방문했을 때 최소 방문 횟수를 나타내고 초기에는 전부 100으로 지정해둔다.
  100번째 칸에 도착할 때까지의 최대 방문횟수는 99이기에 100으로 넣어둔다.
• 이후 bfs 함수를 진행한다. 이때 stack은 방문횟수가 적은 칸부터 확인해줄 것이기에 heap구조로 만들어준다.
• while문에서 heappop으로 방문횟수가 제일 적은 칸을 확인할 것이다.
• 해당 칸에서 이동 횟수를 하나 늘리고 for 문으로 주사위 1~6까지 굴려가며 이동시킨다.
• 현재 위치에서 주사위 눈 수만큼 이동가능하다면 뱀이나 사다리까지 포함해서 new라는 새로운 칸으로 이동한다.
• 해당 new칸의 방문 횟수를 보았을 때 이전에 new칸을 방문했을 때의 방문횟수보다 적게 도착했다면,
  방문횟수를 초기화 해주고 new칸으로 이동해준다.(heappush는 O(logN) append는 O(1)의 시간복잡도를 갖는다.)
  이때 만약 도착했다면 해당 값을 바로 return해주면 된다.
• 방문횟수가 작은 시도 순으로 heappush를 해주기 때문에 처음으로 100번째 칸에 도달하는 순간의 방문횟수는 항상 최소일 수 밖에 없다.