문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

# 13549
import sys
input = lambda: sys.stdin.readline().strip()

# visited
# bfs

from collections import deque

n, k = map(int, input().split())
my_time = [10 ** 9] * 100001
    
def bfs(time = 0):
    global n, k, my_time
    
    queue = deque()
    queue.append((n, time))
    my_time[n] = time
    while queue:
        x, time = queue.popleft()
        
        if x == k:
            continue
        if 0 <= x*2 <= 100000 and my_time[x] < my_time[x*2]:
            my_time[x*2] = time
            queue.appendleft((x*2, time))
        
        if 0 <= x+1 <= 100000 and my_time[x]+1 < my_time[x+1]:
            my_time[x+1] = time + 1
            queue.append((x+1, time+1))
            
        if 0 <= x-1 <= 100000 and my_time[x]+1 < my_time[x-1]:
            my_time[x-1] = time + 1
            queue.append((x-1, time+1))
            
bfs()
print(my_time[k])

백준 13549 숨바꼭질 3