BOJ 128521 2

質問する

BOJ 128521 2
シルバーI|白準12852|Python 3 Pythonプール

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

これは典型的なBFS問題である.BFSはまずサブノードにアクセスするので,同じレベルのサブノードのブラウズ深度は同じである.従って、最短経路を探す場合、BFSはDFSよりも有利である.

BFS

3に分割すると、その値を有するサブアクセス

がある.

2に分割すると、その値を有するサブアクセス

がある.

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)

結果

Python 3はタイムアウトを引き起こす.Pypy 3でコミットする必要があります.