[BOJ]2056 작업- 파이썬

풀이

딕셔너리를 두개를 만들어 주었다.
하나는, 이번 일 이 부모인 딕셔너리와 지금 일이 자식인 딕셔너리 이다.

그렇게 한 다음 선행작업이 아무것도 없는 작업을 가장 먼저 수행한다.
그렇다면 두번째 딕셔너리를 이용해서 다음으로 수행 가능성이 있는 작업을 수행한다.

현재 작업이 끝나는 최소 시간은,
선행작업들의 끝나는 시간의 최대시간 + 현재작업이 걸리는 시간
이된다.

마지막으로 정답은 모든 작업들이 걸리는 시간중 가장 큰값이 된다.

코드

from collections import defaultdict, deque

ans = 0
N = int(input())
q = deque()
values = [0 for _ in range(N+1)]
times = [0 for _ in range(N+1)]
graph = defaultdict(list)
next_nodes = defaultdict(list)
visited = [0 for _ in range(N+1)]
cnt = 0

for i in range(1, N+1):
    arr = list(map(int, input().split(" ")))
    values[i] = arr[0]
    if arr[1] == 0:
        q.append(i)
        continue
    for j in arr[2:]:
        graph[i].append(j)
        next_nodes[j].append(i)

while cnt < N:
    temp = set()
    while q:
        cur = q.popleft()
        needs = graph[cur]
        max_value = 0
        can_go = True
        for need in needs:
            if visited[need] == 0:
                can_go = False
                break
            max_value = max(max_value, times[need])
        if not can_go:
            continue
        times[cur] = values[cur]+max_value
        visited[cur] = 1
        for node in next_nodes[cur]:
            if visited[node] == 0:
                temp.add(node)
    q.extend(list(temp))
    cnt += 1
    print(q)
print(max(times))