문제

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

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

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

from collections import deque

# 1. 위치당 소요시간을 저장하는 리스트 : time
# 2. 최소 소요시간으로 해당 위치를 방문한 횟수 : pos
# 3. 이동 시 해당 위치의 최대 소요시간이 줄어든다면 pos의 값 대입
# 4. 이동 시 해당 위치의 최대 소요시간과 같다면 pos에 값 추가

n, k = map(int, input().split())
time, pos = [-1] * 100001, [-1] * 100001


def bfs(n, k):
    queue = deque()
    queue.append(n)
    time[n], pos[n] = 0, 1
    
    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
                pos[num] = pos[n]
                queue.append(num)
                
            elif time[n] + 1 == time[num]:
                pos[num] += pos[n]
                
                
bfs(n, k)
print(time[k])
print(pos[k])

백준 12851 숨바꼭질 2