문제

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

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

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

from collections import deque

# 1. 위치당 소요시간을 저장하는 리스트 : time
# 경로 저장 과정에서 리스트에 값을 추가해 갱신하는 방법을 사용하면 시간초과가 발생한다.

n, k = map(int, input().split())

time = [-1] * 100001
route = [-1] * 100001


def bfs(n):
    global k
    queue = deque()
    queue.append(n)
    time[n] = 0
    
    while queue:
        n = queue.popleft()
        
        if n == k:
            continue
        
        number = [n*2, n+1, n-1]
        for num in number:
            if num < 0 or num > 100000:
                continue
            if time[num] == -1 or time[n] + 1 < time[num]:
                time[num] = time[n] + 1
                route[num] = n
                queue.append(num)
                
                
bfs(n)
print(time[k])

output = [k]
for _ in range(time[k]):
    output.append(route[k])
    k = output[-1]
output.reverse()
print(*output)

백준 13913 숨바꼭질 4