백준 2056. 작업

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

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
indegree = [0] * (n+1) # 선행 작업 개수 기록
graph = [[] for _ in range(n+1)] # 후행 작업들의 리스트
dp = [0] * (n+1) # 각 작업이 완료되기까지 필요한 최소 시간
t = [0] # 각 작업의 소요 시간 저장

for i in range(1, n+1):
    array = list(map(int, input().split()))
    t.append(array[0])
    if array[1] != 0: # 선행 작업이 있는 경우
        for j in range(2, len(array)):
            graph[array[j]].append(i)
            indegree[i] += 1

q = deque()
# 선행 작업이 없는 작업을 큐에 삽입
for i in range(1, n+1):
    if indegree[i] == 0:
        q.append(i)
        dp[i] = t[i] # 선행 작업 없으므로 본인 수행 시간만

while q:
    now = q.popleft()
    for i in graph[now]:
        indegree[i] -= 1
        dp[i] = max(dp[now] + t[i], dp[i]) # 기존의 값과 현재의 작업을 거칠 경우 비교 ->최댓값 갱신
        if indegree[i] == 0: # 선행 작업을 모두 완료했을 경우
            q.append(i) # 마지막 선행 작업 번호를 넣어 다음 작업 수행(모든 선행작업이 완료되었으므로 준비됐음)
print(max(dp))

선행 작업 개수 리스트, 후행 작업들 리스트, 각 작업의 소요시간 리스트

이렇게 세 개의 리스트를 만들어야된다는 점을 생각해내기가 정말 어렵다.....