[BOJ] 13549. 숨바꼭질3(python)

📌문제

💪아이디어

1. 해당 위치에서 움직이기
   움직이는 방법은 앞으로 걷기(x+1), 뒤로 걷기(x-1), 순간이동하기(2*x)로, 세 가지이다.
   

2. 움직이는 방법별 소모 시간
   걸을 경우 +1, 순간이동할 경우 0의 시간이 소모된다.
   최소의 소모시간을 구하기 위해서는 소모시간이 적게 걸리는 움직이는 방법을 선택해야하기 때문에 min heap을 사용한다.
   

3. 최소의 시간으로 움직이는 방법찾기
   bfs를 사용하는데 min heap을 사용하여 최소의 시간이 걸리는 방법부터 탐색한다.
   (시간, 현재위치)로 요소를 넣는다. hepapop 을 하면 현재위치에서 최소의 시간이 걸리는 요소가 나올 것이기 떄문에 현재위치가 동생위치와 같으면 탐색을 종료한다.
   

🥂코드

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

def bfs():
    move[n] = 0
    heap = []
    heappush(heap,(0, n))

    while heap:
        cnt, cur = heappop(heap)
        if cur == k: 
            print(cnt)
            return
        for opt, c in [(cur+1,1), (cur-1,1), (2*cur,0)]:
            if 0 <= opt <= 100000:
                clock = cnt + c
                if move[opt] > clock:
                    move[opt] = clock
                    heappush(heap,(clock,opt))

n, k = map(int,input().split())
move = [float('inf')] * 100001
bfs()