BOJ 128521 2

質問する

アルゴリズム#アルゴリズム#

[ N, 		# 탐색 깊이
  str(N), 	# 경로 (문자열)
  0		# 자식 노드의 값
]

コード#コード#

import sys
from collections import deque

def BFS(n):
    queue = deque()
    queue.append([n, str(n), 0])

    while queue:
        next, path, time = queue.popleft()
		
        # 1이 되면 깊이와 경로 출력 후 종료
        # BFS는 같은 레벨의 자식의 탐색 깊이가 같으므로
        # 가장 빠르게 도달한 1을 가진 자식 노드가 최단 경로
        if next == 1:
            print(time)
            print(path)
            return
		
        # 3으로 나누어 떨어지면
        if next % 3 == 0:
        	# 자식 노드 방문
            queue.append([next // 3, path + ' ' + str(next // 3), time + 1])
        
        # 2로 나누어 떨어지면
        if next % 2 == 0:
        	# 자식 노드 방문
            queue.append([next // 2, path + ' ' + str(next // 2), time + 1])

        if next > 1:
        	# 1을 뺀 값을 가진 자식 노드 방문
            queue.append([next - 1, path + ' ' + str(next - 1), time + 1])


N = int(sys.stdin.readline())

BFS(N)

結果