[BOJ] 1005번 ACM Craft

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

1005번: ACM Craft

import sys
from collections import deque

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

for _ in range(t):
    n, k = map(int, sys.stdin.readline().split())
    dGraph = [[] for __ in range(n+1)]
    inDeg = [0] * (n+1)
    cost = [0] + list(map(int, sys.stdin.readline().split()))
    costSoFar = [0] * (n+1)
    q = deque()
    
    for __ in range(k):
        a, b = map(int, sys.stdin.readline().split())
        inDeg[b] += 1
        dGraph[a].append(b)
        
    
    for i in range(1, n+1):
        if inDeg[i] == 0:
            q.append(i)
            costSoFar[i] = cost[i]
            
    
    while q:
        now = q.popleft()
        for i in dGraph[now]:
            inDeg[i] -= 1
            costSoFar[i] = max(costSoFar[i], costSoFar[now] + cost[i])	# 1
            if inDeg[i] == 0:
                q.append(i)
                
    ans = int(sys.stdin.readline())
    print(costSoFar[ans])

앞으로 다른 문제에서도 마주칠 법한 알고리즘이다. 

이 문제의 핵심 라인은 # 1 번 줄이다.

cost 배열과는 별개로 costSoFar이라는 배열을 추가로 만들어서 큐를 반복할 때 마다 걸린 시간의 최댓값을 갱신해준다.