[Ch.10 - 그래프 이론] 커리큘럼

My code

from collections import deque
import copy

v = int(input())
indegree = [0] * (v + 1)
graph = [[] for i in range(v + 1)]
time = [0] * (v + 1)

for i in range(1, v + 1):
    data = list(map(int,input().split()))
    time[i] = data[0]
    for x in data[1:-1]:
        graph[x].append(i)
        indegree[i] += 1

def topology_sort():
    q = deque()
    result = copy.deepcopy(time)

    for i in range(1, v + 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] + time[i])
            if indegree[i] == 0:
                q.append(i)

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

topology_sort()

Code Review

이번 문제는 각 온라인 강의의 선수 강의가 존재하고 각 강의의 수강 시간이 주어졌으며, 동빈이가 N 개의 강의를 듣는다고 할 때 수강하기까지 걸리는 최소 시간을 각각 하나씩 출력해보는 것이었습니다.
강의 하나를 노드라고 했을 때 선수 강의가 존재한다는 것은 정해진 순서가 있다는 것이고 이 순서대로 나열해야 한다는 것입니다. 따라서 이는 위상 정렬 알고리즘을 사용하여 해결할 수 있습니다.
또한 각 강의를 수강하기 까지 걸리는 최소 시간을 구하기 위해 강의 각각의 수강 시간을 저장할 time 배열이 필요합니다. 또한 계산한 최소 시간은 result 배열에 저장해주었습니다. 이때 주의해야 할 점은 result 배열을 초기화 할 때 강의 각각의 수강 시간으로 초기화 해주어야 합니다. 따라서 time 배열의 값을 그대로 넣어주어야 하는데, 이처럼 리스트의 값을 복사해야 할 때는 대입 연산이 아닌 deepcopy() 함수를 사용해야 합니다.
위상 정렬 알고리즘은 deque 를 import 하여 구현해주었습니다. 진입 차수 (노드로 들어오는 간선의 개수) 가 0인 노드를 큐에 삽입해주고 큐의 왼쪽에서 원소를 꺼내주는 과정을 반복하며 만약 어떠한 원소가 꺼내졌을 때 해당 노드의 간선을 모두 삭제해주고 (가리키는 노드의 indegree 1 감소) result 값을 구해주었습니다. result 값은 max 함수를 이용해 구할 수 있는데, 현재까지 구한 result[i] 의 값과 현재 노드의 선수 노드에서까지 구한 result[now] 값 + 현재 노드의 강의 시간 time[i] 을 서로 비교하여 더 큰 값을 선택해 result 의 값을 갱신해주었습니다. 그리고 만약 진입 차수의 값이 0이라면 노드로 들어오는 간선의 개수가 없다는 것이므로 큐에 넣어주었습니다. 이 과정을 큐가 모두 빌 때까지 반복해주었습니다.
반복문을 빠져나오면 모든 과정이 완료되었다는 뜻이므로 최종적으로 구한 result 즉, 각 강의의 최소 수강 시간을 출력해주었습니다.