BOJ12852 1로 만들기 2
문제
BOJ12852 1로 만들기 2
실버I | 백준 12852 | Python3 파이썬 풀이
알고리즘
전형적인 BFS 문제이다. BFS는 자식 노드를 먼저 방문하므로, 같은 레벨의 자식 노드들의 탐색 깊이가 같다. 그러므로 최단 경로를 찾을 때는 BFS가 DFS보다 유리하다.
- BFS
- 3으로 나누어 떨어지면 그 값을 가진 자식 방문
- 2로 나누어 떨어지면 그 값을 가진 자식 방문
- 1을 뺀 자식 방문
- 자식 노드가 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로 제출해야 한다.
Author And Source
이 문제에 관하여(BOJ12852 1로 만들기 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehe228/boj12852저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)