[백준] 1005번 ACM Craft - PYTHON

[백준] 1005번 ACM Craft - PYTHON  https://www.acmicpc.net/problem/1005

알고리즘 분류

 

• 다이나믹 프로그래밍
• 그래프 이론
• 위상 정렬

출력

건물 W를 건설완료 하는데 드는 최소 시간을 출력한다. 편의상 건물을 짓는 명령을 내리는 데는 시간이 소요되지 않는다고 가정한다.

건설순서는 모든 건물이 건설 가능하도록 주어진다.

제한

• 2 ≤ N ≤ 1000
• 1 ≤ K ≤ 100,000
• 1 ≤ X, Y, W ≤ N
• 0 ≤ Di ≤ 100,000, Di는 정수

>> 소스 

import sys
from collections import deque
 
T = int(input(" 테스트 케이스 T 입력 : "))
 
for _ in range(T):
    N,K=map(int,input(" 건물수, 건설 순서 : ").split())#건물수, 건설순서규칙
    time=[0]+list(map(int,input(" 각 건물들의 건설시간 : ").split()))#건물들의 건설시간
    seq=[[] 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())
        seq[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]=time[i]
 
    while q:
        a=q.popleft()
        for i in seq[a]:
            inDegree[i]-=1#진입차수 줄이고
            DP[i]=max(DP[a]+time[i],DP[i])#DP를 이용해 건설비용 갱신
            if inDegree[i]==0:
                q.append(i)
 
 
    ans = int(input(" W : "))
    print(DP[ans])

>> 결과

>> ./1005_ACM_Craft.py 
 테스트 케이스 T 입력 : 2
 건물수, 건설 순서 : 4 4
 각 건물들의 건설시간 : 10 1 100 10
 건설순서규칙 : 1 2
 건설순서규칙 : 1 3
 건설순서규칙 : 2 4
 건설순서규칙 : 3 4
 W : 4
120
 건물수, 건설 순서 : 8 8
 각 건물들의 건설시간 : 10 20 1 5 8 7 1 43
 건설순서규칙 : 1 2
 건설순서규칙 : 1 3
 건설순서규칙 : 2 4
 건설순서규칙 : 2 5
 건설순서규칙 : 3 6
 건설순서규칙 : 5 7
 건설순서규칙 : 6 7
 건설순서규칙 : 7 8
 W : 7
39