백준|1005번|ACM Craft

문제 설명

건물들을 짓기 위한 시간과 어떤 건물을 짓기 위해 먼저 지어야 하는 건물들을 입력받고 W번째 건물을 짓는데 걸리는 최소 시간을 출력하는 문제입니다. 이때 건물은 동시에 짓는 것이 가능합니다.

작동 순서

1. 테스트케이스의 개수를 입력받습니다.
2. 건물의 개수 N과, 건물 간의 관계의 개수 M을 입력받습니다.
3. 먼저 지어야 하는 건물 A와 해당 건물을 짓고 나서 지을 수 있는 건물 B를 입력받습니다. A의 그래프에 B를 추가해주고 B를 짓기 위해 필요한 건물의 수를 +1 해줍니다.
4. 현재 건설 가능한 건물부터 지으면서 해당 건물을 필요로 하는 건물들의 필요 건물 수를 -1 해주고 해당 건물들의 건설 시간을 갱신해줍니다.
5. 필요 건물 수가 0이 되는 건물이 있으면 그 건물을 건설 목록에 추가합니다.
6. W번째 건물을 짓는 데 필요한 시간을 출력합니다.

소스코드

import sys
from collections import deque

T = int(sys.stdin.readline())
for t in range(T):
    N, K = map(int, sys.stdin.readline().split())
    time = [0] + list(map(int, sys.stdin.readline().split()))
    need = [0]*(N+1)
    dp = [0]*(N+1)
    graph = [[] for _ in range(N+1)]
    q = deque()

    for i in range(K):
        num1, num2 = map(int, sys.stdin.readline().split())
        graph[num1].append(num2)
        need[num2] += 1

    for i in range(1, N+1):
        if need[i] == 0:
            q.append(i)

    W = int(sys.stdin.readline())
    while q:
        num = q.popleft()
        dp[num] += time[num]
        if num == W:
            print(dp[W])
            break
        for n in graph[num]:
            if dp[n] < dp[num]:
                dp[n] = dp[num]
            need[n] -= 1
            if need[n] == 0:
                q.append(n)