[BaekJoon] 백준 12852번 : 1로 만들기 2

12852번 : 1로 만들기 2

1로 만들기 문제에서 경로까지 추가 된 문제이다.

[BaekJoon] 백준 11779번 : 최소비용 구하기 2 문제 처럼 경로를 다루는 방법은 두 가지가 있다.

지금까지의 모든 경로를 저장하는 방법과 바로 직전에 방문한 노드만 저장하는 방법이 있는데 후자가 훨씬 속도가 빠르다.

이 문제도 BFS 를 통해 탐색하며 경로를 저장하면 된다.

---

from collections import deque


def solution():
    result = []
    queue = deque([N])

    while queue:
        now = queue.popleft()
        if now == 1:
            start, end = 1, visit[1]

            while end:
                result.append(start)
                start = end
                end = visit[start]
            result.append(N)
            result.reverse()
            print(len(result) - 1)
            print(*result)

        if now % 3 == 0 and not visit[now // 3]:
            queue.append(now // 3)
            visit[now // 3] = now
        if now % 2 == 0 and not visit[now // 2]:
            queue.append(now // 2)
            visit[now // 2] = now
        if not visit[now - 1]:
            queue.append(now - 1)
            visit[now - 1] = now


if __name__ == "__main__":
    N = int(input())
    visit = [0] * (N + 1)
    solution()