[백준] 2056번 작업 (파이썬, 위상정렬)

height: 현재 번호 작업을 하기 위한 우선순위 작업들을 담고 있다

cost: 현재 작업의 비용(시간)

 

모든 작업을 돌면서 현재 번호를 작업하기 위해 먼저 해야할 작업들의 비용의 최대값(여러 작업을 동시에 할 수 있다는 조건이 있다)에 현재 작업의 시간을 더한 것이 현재 번호를 작업하는 걸리는 시간이다 

from collections import defaultdict
import heapq

height=defaultdict(list)
cost=defaultdict(int)

n=int(input())
for i in range(1,n+1):
    c=list(map(int,input().split()))
    cost[i]=c[0]
    if c[1]==0: continue
    for j in c[2:]:
        height[i].append(j)
        
for i in range(1,n+1):
    temp=0 # 현재 번호 i에서의 이전 작업들 중 최대 걸린 시간 
    for j in height[i]:
        temp=max(temp,cost[j])
    cost[i]+=temp

print(max(cost.values()))