#13913

이전의 숨바꼭질 문제와 동일한 로직이다. 똑같이 풀면 된다.

하지만 이번 문제에서는 방문했던 모든 경로를 기억해야한다. 이걸 어떻게 해줘야 할 지 한참을 생각했다.

결론은 단순했다. 원소를 넣을 때(nx) 그게 어디서부터 왔는지(X)를 기록해두면 된다.

출력할 때는 거꾸로 타고 올라가면 된다.

예를 들어 17을 찾는 문제라면
17은 어디서 왔는데? => 18
18은 어디서 왔는데? => 9
9는 어디서 왔는데? => 10
10은 어디서 왔는데? => 5

제일 처음에 5는 어디서 왔는데? 에 해당하는 pathList[5] 를 -1로 초기화 해두고 출력할 때의 반복문 while 의 break 조건을 -1로 두면 된다.

from collections import deque
import sys
input = sys.stdin.readline

MAX = 100000

N, K = map(int, input().split())
visit = [0 for i in range(0, MAX+1)]
pathList = [0 for i in range(0, MAX+1)]
answerList = deque()

def bfs():
    queue = deque()

    queue.append((N,0))
    pathList[N] = -1
    visit[N] = 1

    while queue:
        # input()
        X, nowTime = queue.pop()
        # print("X = ", X)
        if X == K:
            # print("찾았음")
            # 타고온 경로를 어떻게 기억해주냐? 
            print(nowTime)
            idx = K
            while (1):
                val = pathList[idx]
                # print("idx = ", idx)
                answerList.appendleft(idx)
                # print(idx, " 는 ", val, " 에서 왔어 ")
                # print(val)
                # val = 18, idx = 17
                if val == -1:
                    # print("val이 -1 이네 ?")
                    break
                idx = val
            print(*answerList)
            break

        
        for nx in [2*X, X+1, X-1]:
            if 0 <= nx <= MAX and visit[nx] == 0:
                visit[nx] = 1
                queue.appendleft((nx, nowTime+1))
                pathList[nx] = X
                # print(nx, " 는 ", X, " 으로 부터 왔어 ")

bfs()