[Python] boj no. 2056 : 작업

Problem

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

Idea

전형적인 위상 정렬 문제이다. 힙을 이용하여 풀이했다.

Code

import sys
import heapq

input = sys.stdin.readline

N = int(input())
edge = [[] for _ in range(N+1)]
parent = [0 for _ in range(N+1)]
weight = [0 for _ in range(N+1)]

for i in range(1, N+1):
    line = list(map(int, input().split()))
    weight[i] = line[0]
    parent[i] = line[1]
    for j in range(0, line[1]):
        edge[line[2+j]].append(i)

heap = []
time = 0
for i in range(1, N+1):
    if parent[i] == 0:
        heapq.heappush(heap, (weight[i], i))
        
while heap:
    time, cur_node = heapq.heappop(heap)
    
    for nn in edge[cur_node]:
        parent[nn] -= 1
        if parent[nn] == 0:
            heapq.heappush(heap, (time+weight[nn], nn)) 

print(time)

Comment