백준 1005 ACM Craft

먼저, 어떤 건물순으로 지을 수 알 수 없기 때문에 위상정렬을 통해 지을 건물들의 순서를 구한다.

order = topology_sort()

그 다음 이전 깊이에서 최댓값을 구해 현재 노드에서 걸리는 시간을 더해 준다.

    for i in order:
        max = 0
        for j in rgraph[i]:
            if D[j] > max:
                max = D[j]
        D[i] = max + costs[i]

전체 코드는 다음과 같다.

import sys
from collections import deque

def topology_sort():
    global indegree
    result = []
    q = deque()
    
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)
    
    while q:
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
    return result

N = int(sys.stdin.readline())

for _ in range(N):
    v,e = map(int, sys.stdin.readline().split())
    costs = [0] + list(map(int, sys.stdin.readline().split()))
    graph = [[] for i in range(v+1)]
    rgraph = [[] for i in range(v+1)]
    indegree = [0] * (v+1)
    
    for _ in range(e):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        rgraph[b].append(a)
        indegree[b] += 1
    
    K = int(sys.stdin.readline())
    D = [0]*(v+1)
    
    order = topology_sort()
    for i in order:
        max = 0
        for j in rgraph[i]:
            if D[j] > max:
                max = D[j]
        D[i] = max + costs[i]
    print(D[K])