[문제]

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

[코드]

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

t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    d = list(map(int, input().split()))
    d.insert(0, 0)
    graph = [[] for j in range(n + 1)]
    indegree = [0] * (n + 1)
    for j in range(k):
        x, y = map(int, input().split())
        graph[x].append(y)
        indegree[y] += 1
    w = int(input())

    dp = [0] * (n + 1)
    q = deque()
    for j in range(1, n + 1):
        if indegree[j] == 0:
            q.append(j)
            dp[j] += d[j]

    while q:
        now = q.popleft()

        for j in graph[now]:
            indegree[j] -= 1
            dp[j] = max(dp[j], dp[now] + d[j])
            if indegree[j] == 0:
                q.append(j)

    print(dp[w])

[풀이]

이 문제는 위상정렬과 dp를 이용해서 해결할 수 있다

먼저 파라미터들을 입력받은 후 dp와 queue를 정의한다. 그런 다음 indegree가 0인 루트를 queue에 접어넣는다

그리고 queue에서 값을 꺼내고, 꺼낸 값과 연결된 간선의 indegree를 -1씩 하면서 dp테이블에 최대값을 수정한다

이러한 로직으로 진행하면 간선에서 들어오는 노드는 max의 dp값을 계속 업데이트 하기 때문에 문제가 해결된다