[10-09 그래프] 커리큘럼

최근 보고 있는 책인  '이것이 코딩테스트다 with 파이썬 편_나동빈_한빛미디어' 에 있는 문제이다.

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

 

문제는 책 안에 있다!! 이는 topology sort를 활용하면 좋을 것 같다고 생각하였고, 책을 통해 개념을 알아가는 부분이기 때문에 책을 많이 참고하였다.

 

 

import sys
from collections import deque
import copy

input = sys.stdin.readline
n = int(input())
indegree = [0] *(n+1)
graph = [[] for i in range(n+1)]
duration = [0] * (n+1)

for i in range(1,n+1):
    data = list(map(int,input().split()))
    duration[i] = data[0]
    for j in data[1:-1]:
        indegree[i] += 1
        # 선수 과목에 현재 과목 꼬리달기
        graph[j].append(i)

def topology_sort() :
    result=copy.deepcopy(duration)
    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]:
            result[i] = max(result[i], result[now]+duration[i])
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    for i in range(1,n+1):
        print(result[i])


topology_sort()