문제

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

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

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

---

문제풀이

• 방문처리 배열, 시간기록 배열 생성
• 방문처리 배열에 전 위치 기록
• 동생을 찾은 경우, 방문처리 배열에 기록을 타고 가서 수빈이 위치까지 도달한 것을 출력

Code

from collections import deque

MAX_VALUE = 100000

n, k = map(int, input().split())
queue = deque()
visited = [-1 for _ in range(MAX_VALUE+1)]
count = [0 for _ in range(MAX_VALUE+1)]
queue.append(n)
visited[n] = n

while queue:
    x = queue.popleft()
    if x == k:
        print(count[k])
        break
    if x - 1 >= 0 and visited[x-1] == -1:
        queue.append(x-1)
        visited[x-1] = x
        count[x-1] = count[x] + 1
    if x + 1 <= MAX_VALUE and visited[x+1] == -1:
        queue.append(x+1)
        visited[x + 1] = x
        count[x+1] = count[x] + 1
    if x*2 <= MAX_VALUE and visited[x*2] == -1:
        queue.append(x*2)
        visited[x*2] = x
        count[x*2] = count[x] + 1

arr = []
while n != k:
    arr.append(k)
    k = visited[k]
arr.append(n)
print(*arr[::-1])

주의

수빈이와 동생의 위치가 0부터 가능
바보같이 방문처리 배열을 0으로 초기화했다가 계속 50%에서 시간초과 뜸...