백준 1005 ACM Craft

위상정렬을 이용한 문제이다.
어떤 정점에 연결된 in-degree를 이용해 각 정점의 차수를 줄여나가는 방식으로 문제를 해결할 수 있다.

문제를 해결한 방식은,
입력값으로 들어오는 연결을 그래프로 만들어 주고, in-degree값을 증가시켜 차수의 배열을 만들어 주었다.
이제 배열을 돌면서 차수가 0인 인덱스를 큐에 넣은 뒤, 각 정점을 꺼내면서 문제를 해결하면 된다.
또한 이 문제에서는 어떤 정점이 2개의 차수를 가지고 있을 때, 2개의 정점 각각 시간이 같이 흐른다는 점을 처리해주어야 한다.
잘 생각해보면 2개의 차수를 가지고 있는 지점에서 1개의 차수가 끝난다고 하더라도, 다른 차수가 늦게 끝나면 기다려야 한다. 그렇기 때문에 현재 건물 완성시간 + 이전 건물을 짓는데 완성시간과 현재 건물을 짓는데 완성시간을 비교하여 큰 값을 택하면 된다.
dp를 이용한 개념을 적용했다고 봐도 될 것 같다.

from collections import deque
import copy
t = int(input())
for _ in range(t):
    n,k = map(int,input().split())
    build_time = [0]
    build_time.extend(list(map(int,input().split())))
    graph = [[] for i in range(n+1)]
    degree = [0]*(n+1)
    complete_time = copy.deepcopy(build_time)
    for i in range(k):
        a,b = map(int,input().split())
        degree[b] += 1
        graph[a].append(b)
    w = int(input())
    queue = deque([])
    for i in range(1,n+1):
        if degree[i] == 0:
            queue.append(i)

    while queue:
        idx = queue.popleft()
        for element in graph[idx]:
            degree[element] -= 1
            complete_time[element] = max(complete_time[element], build_time[element] + complete_time[idx])
            if degree[element] == 0:
                queue.append(element)
    print(complete_time[w])