[알고리즘/백준] 13913번 : 숨바꼭질 4(python)

숨바꼭질 1에서 이동했던 위치를 기록해줄 리스트 하나를 더 만들어준다.
위치에 도달하면 기록했던 리스트를 하나씩 가져와 역순으로 출력한다.

from collections import deque


def move(x):
    a = []
    t = x
    for _ in range(visited[x]+1):
        a.append(t)
        t = m[t]
    print(' '.join(map(str, a[::-1])))


def bfs(x):
    q = deque()
    q.append(x)
    while q:
        x = q.popleft()
        if x == K:
            print(visited[x])
            move(x)
            break
        for nx in (x - 1, x + 1, x * 2):
            if 0 <= nx < 100001 and not visited[nx]:
                q.append(nx)
                visited[nx] = visited[x] + 1
                m[nx] = x


N, K = map(int, input().split())
visited = [0] * 100001
m = [0] * 100001
bfs(N)