[골드3] 1005번 : ACM Craft

🛠 문제

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

👩🏻‍💻 해결 방법

dp를 적용하여 구하는 위상정렬 문제였다
q에서 값을 뺄 때, 진입차수-1과 동시에 dp[now](이전 건물까지 걸리는 시간)+d[i](이번 건물을 짓는 시간)와 dp[i] 중 더 큰 값을 dp[i]에 저장해주었다
해당 건물이 지어지기 위해서는 앞에 지어질 건물에 드는 시간들 중 가장 긴 시간에 맞춰주어야 모든 건물을 짓고 해당 건물을 지을 수 있기 때문이다

소스 코드

import sys
from collections import deque
input = sys.stdin.readline

T = int(input())
for _ in range(T):
  n, k = map(int, input().split())
  d = [0] + list(map(int, input().split()))
  graph = [[] for _ in range(n+1)]
  indegree = [0 for _ in range(n+1)]
  dp = [0 for _ in range(n+1)]

  for _ in range(k):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1
  
  q = deque()
  for i in range(1, n+1):
    if indegree[i] == 0:
      q.append(i)
      dp[i] = d[i]
  
  while q:
    now = q.popleft()
    for i in graph[now]:
      indegree[i] -= 1
      dp[i] = max(dp[i], dp[now] + d[i])
      if indegree[i] == 0:
        q.append(i)
  
  target = int(input())
  print(dp[target])