728x90
반응형
https://www.acmicpc.net/problem/13549
※ BFS로 풀면 메모리 초과 나서, 또익스트라로 풂
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
N, K = map(int, input().rstrip().split())
distance = [INF]*100001
def hide_and_seek():
queue = []
heapq.heappush(queue, (0, N))
while queue:
weight, now = heapq.heappop(queue)
if now == K:
distance[now] = weight
return
if distance[now] < weight:
continue
next_now = now - 1
cost = weight + 1
if (next_now >= 0) and (distance[next_now] > cost):
distance[next_now] = cost
heapq.heappush(queue, (cost, next_now))
next_now = now + 1
cost = weight + 1
if (next_now <= 100000) and (distance[next_now] > cost):
distance[next_now] = cost
heapq.heappush(queue, (cost, next_now))
next_now = now * 2
cost = weight
if (0 <= next_now <= 100000) and (distance[next_now] > cost):
distance[next_now] = cost
heapq.heappush(queue, (cost, next_now))
hide_and_seek()
print(distance[K])
728x90
반응형
'Algorithm > Baekjoon' 카테고리의 다른 글
BOJ 5944 Apple Delivery Java (1) | 2024.04.12 |
---|---|
BOJ 1916 최소비용 구하기 Python3 (0) | 2023.07.15 |
BOJ 11404 플로이드 Python3 - 플로이드 워셜 알고리즘 (0) | 2023.07.15 |
BOJ 1753 최단경로 Python3 - 다익스트라 알고리즘 (0) | 2023.07.15 |
BOJ 2606 바이러스 Python3 (0) | 2023.07.06 |