파이썬 백준 2056 작업

import sys
input = sys.stdin.readline
from collections import deque
 
Vn = int(input())
V = {}
for i in range(1, Vn + 1) : 
    V[i] = []
B = [0 for i in range(Vn + 1)]
parent = [0 for i in range(Vn + 1)]
for i in range(1, Vn + 1) : 
    l = list(map(int, input().split()))
    B[i] = l[0]
    for j in range(2, len(l)) : 
        V[l[j]].append(i)
    parent[i] = parent[i] + len(l) - 2
 
que = deque()
for i in range(1, Vn + 1) : 
    if parent[i] == 0 : 
        que.append(i)
 
D = B[:]
while que : 
    now = que.popleft()
    for next in V[now] : 
        D[next] = max(D[next], D[now] + B[next])
        parent[next] = parent[next] - 1
        if parent[next] == 0 : 
            que.append(next)
print(max(D))

인풋대로 정렬관계 dict를 작성하고 degree의 갯수를 센다.

degree가 0인 점부터 빌드에 걸리는 시간을 확정하여 연결된 점들의 빌드 시간을 갱신한다.

BFS를 마치면 모든 점의 빌드 시간이 D에 기록되었으므로 max D를 출력한다.