이번 문제는 BFS를 통해 해결하였다. 처음에는 큐에 각각의 방문 경로를 담은 리스트를 함께 담아 구현하였는데, 시간초과가 발생하였다. 그래서 방문 경로를 전역 리스트 하나에 담기로 하였다. 조건을 만족하는 다음 좌표에 대한 before_node를 현재 좌표로 저장해주도록 하였다. 그리고 도착점에 도달하면, 현재 위치에서 가리키는 좌표를 계속해서 따라가도록 하였다. 이 과정이 끝나면 하나의 정답 리스트가 만들어지고, 이를 거꾸로 뒤집어주어 반환하였다.

Code

from collections import deque
n, k = map(int, input().split())
dw, dt = [-1, 1, 0], [1, 1, 2]
visited = [0 for _ in range(max(n, k)+2)]
before_node = [0 for _ in range(max(n, k)+2)]
def find_path(x):
    result = []
    tmp = x
    for _ in range(visited[x]+1):
        result.append(tmp)
        tmp = before_node[tmp]
    return result[::-1]
def catching():
    q = deque()
    q.append(n)
    while q:
        cur = q.popleft()
        if cur == k:
            return find_path(cur)
        for i in range(3):
            nxt = (cur+dw[i])*dt[i]
            if 0 <= nxt < max(n, k)+2 and not visited[nxt]:
                visited[nxt] = visited[cur]+1
                before_node[nxt] = cur
                q.append(nxt)
answer = catching()
print(len(answer)-1)
print(*answer)