[백준] 1005 ACM Craft (Python)

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

import sys
from collections import deque

input = sys.stdin.readline

test_case = int(input())
for _ in range(test_case):
    building, rule = map(int, input().split())
    time = list(map(int, input().split()))

    indegree = [0] * building
    graph = [[] for _ in range(building)]
    for _ in range(rule):
        a, b = map(int, input().split())
        graph[a - 1].append(b - 1)
        indegree[b - 1] += 1

    dest = int(input()) - 1

    queue = deque([])
    dp = [-1] * building

    # 진입 차수가 0인 정점찾기
    for i in range(building):
        if indegree[i] == 0:
            queue.append(i)
            dp[i] = time[i]

    while queue:
        node = queue.popleft()
        if node == dest:
            break

        for near in graph[node]:
            dp[near] = max(dp[near], dp[node] + time[near])
            indegree[near] -= 1
            
            # 해당 건물을 짓기 전에 지어야하는 모든 건물을 지었을 때 append
            if indegree[near] == 0:
                queue.append(near)

    print(dp[dest])

DP와 위상정렬을 사용해 푸는 문제이다.
위상정렬은 이 문제를 통해 처음 접해봤다.

위상정렬이란
사이클이 없는 방향 그래프에서의 노드를 간선의 방향에 따라 한 방향으로 정렬하는 것을 의미한다.