커리큘럼

 

해결법

이 문제는 위상 정렬로 풀면 되는 문제이다. 위상 정렬로 구현은 잘 했지만 디테일한 해결법은 생각하지 못했다. 처음에 각 과목이 걸리는 시간을 저장한 리스트를 만든 다음에 현재 노드에서의 시간과 다음으로 할 과목의 시간을 더한 값을 리스트에 갱신하면서 해결하면 된다. 이때 copy 라이브러리에서 deepcopy 함수를 사용한다. 이것을 사용하지 않으면 얕은 복사가 이루어져서 값이 꼬이게 된다. 자세한건 코드에서 보면 될 것 같다.

코드

from collections import deque
import copy

n = int(input())

indegree = [0] * (n+1)
graph = [[] for i in range(n+1)]
weight = [0] * (n+1)

for i in range(1, n+1):
    ary = list(map(int, input().split()))
    weight[i] = ary[0]

    for j in range(1, len(ary)):
        if ary[j] == -1:
            break
        indegree[i] += 1
        graph[ary[j]].append(i)

result = copy.deepcopy(weight)

q = deque()
for i in range(1, n+1):
    if indegree[i] == 0:
        q.append(i)

while q:
    now = q.popleft()

    for i in graph[now]:
        indegree[i] -= 1
        result[i] = max(result[i], result[now] + weight[i])

        if indegree[i] == 0:
            q.append(i)

for i in result:
    print(i)