[Python] 백준 1005. ACM Craft

https://www.acmicpc.net/problem/1005

1005번: ACM Craft

위상정렬 + bfs를 적용한 느낌의 문제.

 

 

	import sys
	import heapq
	from collections import defaultdict
	def solve(precede_list, build_next, time, target):
	# 조건 없이 바로 만들 수 있는 건물들 찾기
	queue = [(time[idx], idx) for idx in range(1, len(precede_list)) if precede_list[idx] == 0]
	# 시간순서로 정렬. 가장 시간 짧은 것부터 뽑아내는 min heap 사용
	heapq.heapify(queue)
	while queue:
	# 현재 시간에 건설 끝난 건물.
	finish_time, building = heapq.heappop(queue)
	# 완성한 건물이 target 건물이면 그동안 building한 시간 반환
	if building == target:
	return finish_time
	# 지을 수 있는 다음 건물들 정보를 확인한다.
	for next_possible in build_next[building]:
	# 조건에 해당하는 건물 제거
	precede_list[next_possible] -= 1
	# 모든 조건이 해금되어 건물을 지을 수 있는 경우
	# (지금까지 걸린 시간 + 건물 완성할 때까지 걸리는 시간, 건물) 을 heappush
	if precede_list[next_possible] == 0:
	heapq.heappush(queue, (finish_time + time[next_possible], next_possible))
	test_case = int(sys.stdin.readline())
	for _ in range(test_case):
	N, K = map(int, sys.stdin.readline().split())
	# 해당 index 건물을 짓기 위한 prerequisite 개수
	precede_list = [0 for _ in range(N+1)]
	# 해당 건물을 지으면 해금할 수 있는 건물 dictionary
	build_next = defaultdict(list)
	# 해당 index 건물을 짓는 데 걸리는 시간
	time = list(map(int, sys.stdin.readline().split()))
	time.insert(0, 0)
	for _ in range(K):
	precede, antecede = map(int, sys.stdin.readline().split())
	precede_list[antecede] += 1
	build_next[precede].append(antecede)
	target = int(sys.stdin.readline())
	print(solve(precede_list, build_next, time, target))

view raw [백준] ACM Craft.py hosted with ❤ by GitHub