[백준 파이썬 1005번 ACM Craft] 위상정렬

위상정렬이랑 DP를 활용하여 푸는 문제였다

위상정렬로 순서를 정하고 dp를 하는 것보다 위상정렬을 하면서 dp를 계산해나가면 되는 문제

 

25. 위상 정렬(Topology Sort)

25. 위상 정렬(Topology Sort)

위상정렬은 우선순위가 있는 작업들의 순서를 정렬할 때 사용되는 알고리즘이다

DAG Directed Acyclic Graph 유향 비순환 그래프에서만 사용 가능하다 (사이클일 경우 사용 불가)

왜죠?

순환 그래프의 경우 모두 연결되어 있어서 사이클 내에서는 시작점을 찾을 수 없기 때문이다

 

시간복잡도는 O(V+E) 매우 빠른 편

 

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

1005번: ACM Craft

import sys
from collections import deque

input = sys.stdin.readline
T = int(input())

for _ in range(T):
    N, K = map(int, input().split())
    time = list(map(int, input().split()))

    graph = [[] for i in range(N+1)]
    connect = [0 for i in range(N+1)]
    for _ in range(K):
        a, b = map(int, input().split())
        graph[a].append(b)
        connect[b] += 1

    goal = int(input())

    q = deque()
    dp = [0 for _ in range(N+1)]

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

    while q:
        start = q.popleft()
        dp[start] += time[start-1]

        for g in graph[start]:
            connect[g] -= 1
            dp[g] = max(dp[g], dp[start])
            if connect[g] == 0:
                q.append(g)

    print(dp[goal])