[Python]위상정렬 백준 1005

   문제

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

동적계획법을 적용하여 구하는 위상정렬이다.

위상 정렬에서 큐에서 값들을 뺄때 진입차수 뿐만 아니라 이전 건물까지 걸리는 

시간+이번 건물을 짓는 시간과 이전 DP값을 비교하여 더 오래 걸리는시간으로 갱신해

주면된다. 해당 건물이 지어지기위해서는 앞에 지어질 건물들의 걸리는 시간들 중에서 

가장 긴 시간에 맞춰주어야 모든 건물을 짓고 해당 건물을 지을 수 있기 때문이다.

import sys
from collections import deque
 
T=int(sys.stdin.readline())
 
for _ in range(T):
    N,K=map(int,sys.stdin.readline().split())#건물수 건물간의 건설순서규칙
    building=[0]+list(map(int,sys.stdin.readline().split()))#각 건물들의 건설시간
    tree=[[] 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,sys.stdin.readline().split())
        tree[a].append(b)
        inDegree[b]+=1
 
    q = deque()
    for i in range(1,N+1):#진입차수 0인거 찾아서 큐에 넣기
        if inDegree[i]==0:
            q.append(i)
            DP[i]=building[i]
 
    while q:
        a=q.popleft()
        for i in tree[a]:
            inDegree[i]-=1#진입차수 줄이고 비용갱신
            DP[i]=max(DP[a]+building[i],DP[i])#DP를 이용해 건설비용 갱신
            if inDegree[i]==0:
                q.append(i)
 
 
    answer=int(sys.stdin.readline())
    print(DP[answer])