[BOJ] 13549. 숨바꼭질 3 (🥇, BFS/다익스트라)

문제

풀이

🎯 다익스트라 풀이

이동 방식에 따라 가중치가 다르기 때문에 다익스트라 최단경로 알고리즘을 통해 풀이했다.

우선순위 큐(힙 자료구조 사용)를 사용했기 때문에 가장 짧게 걸리는 시간을 먼저 꺼내서 탐색을 진행하게 된다. 방문처리는 현재 탐색을 진행하려는 위치(x)까지의 시간(visited[x])이 함께 꺼내진 현재까지의 시간(dist)보다 더 작거나 같을 경우에만 탐색을 진행하는 것으로 처리한다. 더 오랜 시간이 걸릴 경우 1. 이미 더 짧은 시간으로 방문했고, 2. 더 오랜 시간이 걸리는 경우는 방문할 이유가 없기 때문

# 숨바꼭질 3

import heapq

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

def sol():
    if N >= K:
        return N-K
    
    visited = [1e9]*100001
    visited[N] = 0
    pq = [(0, N)]

    while pq:
        dist, x = heapq.heappop(pq)

        if visited[x] != dist:
            continue
        
        if x+1 < 100001 and visited[x+1] > dist+1:
            visited[x+1] = dist+1
            heapq.heappush(pq, (dist+1, x+1))
        if x-1 > -1 and visited[x-1] > dist+1:
            visited[x-1] = dist+1
            heapq.heappush(pq, (dist+1, x-1))
        if 2*x < 100001 and visited[2*x] > dist:
            visited[2*x] = dist
            heapq.heappush(pq, (dist, 2*x))
    
    return visited[K]

print(sol())