import heapq
INF = int(1e9)
n, k = map(int, input().split())
start = n
d = [INF] * (100001)
q = []
heapq.heappush(q, (0, n))
d[n] = 0
while q:
dist, now = heapq.heappop(q)
if d[now] < dist:
continue
for y in [now-1, now+1, 2*now]:
if y > 100000 or y < 0:
continue
if y == 2*now:
cost = dist
else:
cost = dist + 1
if cost < d[y]:
d[y] = cost
heapq.heappush(q, (cost, y))
print(d[k])
다익스트라 : 그래프는 만들지 않았지만 이동 가능한 곳이 정해져있어서 아래쪽을 약간 변형함. 순간이동은 가중치 0, 아닌 건 가중치 1
from collections import deque
n, k = map(int, input().split())
check = [-1] * (100001)
q = deque()
check[n] = 0
q.append(n)
while q:
x = q.popleft()
for y in [x-1, x+1, 2*x]:
if y < 0 or y > 100000:
continue
if y == 2*x:
tmp = check[x]
else:
tmp = check[x] + 1
if check[y] == -1 or check[y] > tmp:
check[y] = tmp
q.append(y)
print(check[k])
bfs : 탐색하는데 만약 check의 값이 크다면 갱신해주었다. 그래서 최단거리를 구함
while q:
x = q.popleft()
# 순서를 2*x를 가장 앞에 둬서 가중치를 표현한다
for y in [2*x, x-1, x+1]:
if y < 0 or y > 100000:
continue
if y == 2*x:
tmp = check[x]
else:
tmp = check[x] + 1
if check[y] == -1:
check[y] = tmp
q.append(y)
while 문을 이렇게 고쳐서 가중치를 표현함. bfs에서 리스트의 순서의 중요성 다시 한번 생각하기