백준 13913. 숨바꼭질 4

https://www.acmicpc.net/problem/13913

from collections import deque


def bfs(n, k):
    MAX = 100000
    arr = [-1] * (MAX + 1)  # 최단 거리(시간) 저장
    prev = [-1] * (MAX + 1)  # 이전 위치를 저장하는 배열 (경로 역추적)

    q = deque()
    q.append(n)
    arr[n] = 0  # 시작점 방문

    while q:
        v = q.popleft()

        if v == k:  # 목표 지점 도달하면 종료
            path = []
            while v != -1:
                path.append(v)
                v = prev[v]  # 이전 위치 따라가며 역추적
            return arr[k], path[::-1]  # 경로를 올바른 순서로 반환

        for next_v in (v - 1, v + 1, 2 * v):
            if 0 <= next_v <= MAX and arr[next_v] == -1:
                arr[next_v] = arr[v] + 1
                prev[next_v] = v  # 이전 위치 저장 (경로 추적용)
                q.append(next_v)


n, k = map(int, input().split())
time, path = bfs(n, k)

print(time)  # 최소 시간 출력
print(" ".join(map(str, path)))  # 경로 출력

[체크포인트]

bfs 경로 추적은 바로 이전 위치를 저장하는 배열을 하나 만들어서

목표 지점에 도달했을 경우 그 경로를 역추척해서 새로운 빈 리스트에 하나씩 넣은다음 뒤집으면 된다!