백준 2056 작업

from collections import deque

n = int(input())
forward = [[] for _ in range(n+1)]
howmany = [0] * (n+1)
time = [0] * (n+1)
for i in range(1, n+1):
    a, b, *c = map(int, input().split())
    time[i] = a
    for j in range(b):
        forward[c[j]].append(i)
        howmany[i] += 1
d = [0] * (n+1)

q = deque()
work = []

for i in range(1, len(howmany)):
    if howmany[i] == 0:
        q.append(i)
        d[i] = time[i]

while q:
    print(d)
    x = q.popleft()
    work.append(x)
    for j in forward[x]:
        howmany[j] -= 1
        d[j] = max(d[j], d[x] + time[j])
        if howmany[j] == 0:
            q.append(j)
print(work)
print(max(d))

위상정렬과 dp
앞에서 선행 작업의 합을 누적해서 더해준다(그 중 가장 큰 것)
처음에 선행작업이 0개인 작업이 항상 1개인줄 알고

d = [0] * (n+1)
d[1] = time[1]

이렇게 했는데 다시 보니까 반드시 하나 이상 존재한다고 그랬다