[Python] boj no. 1005 : ACM Craft

Problem

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

Idea

순서가 있는 일련의 작업을 차례대로 수행해야 하는 전형적인 위상 정렬 문제이다.

한 건물 B가 건설되기 위해서는 B에 대한 이전 건물이 모두 지어져야 한다. 따라서 B의 건설완료 시간은 B의 건설시간 + B의 이전 건물 중 가장 늦은 건설완료 시간이 된다. 따라서 최소 힙을 이용하여 건설 시작시간이 빠른 순으로 건설하면서 위상 정렬을 구현하였다.

Code

import sys
import heapq

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N, K = map(int, input().split())
    time = [0] + list(map(int, input().split()))
    edge = [[] for _ in range(N+1)]
    degree = [0 for _ in range(N+1)]
    for _ in range(K):
        u, v = map(int, input().split())
        edge[u].append(v)
        degree[v] += 1
    
    obj = int(input())

    heap = []
    for i in range(1, N+1):
        if degree[i] == 0:
            heapq.heappush(heap, (time[i], i))
        
    while heap:
        pt, pn = heapq.heappop(heap)
        if pn == obj:
            print(pt)
            break
        
        for nn in edge[pn]:
            degree[nn] -= 1
            if degree[nn] == 0:
                heapq.heappush(heap, (pt+time[nn], nn))

Comment