BOJ12852 1로 만들기 2

문제

BOJ12852 1로 만들기 2
실버I | 백준 12852 | Python3 파이썬 풀이

알고리즘

전형적인 BFS 문제이다. BFS는 자식 노드를 먼저 방문하므로, 같은 레벨의 자식 노드들의 탐색 깊이가 같다. 그러므로 최단 경로를 찾을 때는 BFS가 DFS보다 유리하다.

1. BFS
2. 3으로 나누어 떨어지면 그 값을 가진 자식 방문
3. 2로 나누어 떨어지면 그 값을 가진 자식 방문
4. 1을 뺀 자식 방문
5. 자식 노드가 1 값을 가지고 있다면 경로와 깊이 출력 후 종료

Queue에는 다음과 같이 정보를 보관한다.

[ 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)

결과

Python3로는 시간 초과가 발생한다. Pypy3로 제출해야 한다.