이번 문제는 BFS를 통한 그래프 탐색으로 해결하였다. 초반에 뼈대는 바로 작성하였지만 예외처리를 하는 부분에서 시간이 오래 걸렸다. n이 k보다 큰 경우와 n이 0이고, k가 1인 경우에만 bfs함수에서 None이 반환되었다. 그래서 이 경우에 대한 예외처리를 진행하였고, 이를 통해 문제를 해결할 수 있었다. 경로의 경우에는 deque에 리스트를 넣어 따로 따로 관리되도록 하였다.

• n, k를 입력받는다.
• 걷는 경우와 순간 이동의 경우를 저장한 리스트 dw, dt를 선언한다.
• bfs함수를 선언한다.
  -> 방문 처리에 사용할 리스트 visited를 2*(k-1)+1의 크기로 선언하고 False로 채운다.
  -> visited[n]을 True로 갱신한다.
  -> q를 deque로 선언한다.
  -> q에 (0, n, [n])을 넣는다.
  -> q가 존재하는 동안 반복하는 while문을 돌린다.
  --> q에서 time, cur, path를 추출한다.
  --> 만약 cur이 k와 같을 경우,
  ---> [time, path]를 반환한다.
  --> 3번 반복하는 i에 대한 for문을 돌린다.
  ---> nxt를 (cur+dw[i])*dt[i]로 선언한다.
  ---> 만약 nxt가 0 이상, 2*(k-1) 이하이고, visited[nxt]가 False일 경우,
  ----> visited[nxt]를 True로 갱신한다.
  ----> q에 (time+1, nxt, path+[nxt])를 넣는다.
• 만약 n이 k보다 클 경우,
  -> n-k를 출력한다.
  -> n부터 k까지의 수를 언팩킹하여 출력한다.
• 만약 n이 0이고, k가 1일 경우,
  -> k-n을 출력한다.
  -> n, k를 출력한다.
• 그 외의 경우,
  -> bfs()의 반환값을 answer에 저장한다.
  -> answer[0]을 출력한다.
  -> answer[1]을 출력한다.

Code

from collections import deque
n, k=map(int, input().split())
dw=[1, -1, 0]
dt=[1, 1, 2]
def bfs():
    visited=[False for _ in range(2*(k-1)+1)]
    visited[n]=True
    q=deque()
    q.append((0, n, [n]))
    while q:
        time, cur, path=q.popleft()
        if cur==k:
            return [time, path]
        for i in range(3):
            nxt=(cur+dw[i])*dt[i]
            if 0<=nxt<=2*(k-1) and not visited[nxt]:
                visited[nxt]=True
                q.append((time+1, nxt, path+[nxt]))
if n>k:
    print(n-k)
    print(*list(range(n, k-1, -1)))
elif n==0 and k==1:
    print(k-n)
    print(*[n, k])
else:
    answer=bfs()
    print(answer[0])
    print(*answer[1])