[그래프] 커리큘럼

1. 문제 설명

N개의 강의 중 선수 강의가 있을 경우 특정 강의가 주어졌을 때, 해당 강의를 듣기 위해서 걸리는 최소한의 시간을 구하는 문제

- 위상정렬을 이용하는 문제로 위상정렬 이론에서는 리턴하는 값이 순서였다면, 이번에는 cost이다. 하지만 알고리즘 상에서 큰 변경점은 없다. 단지, 시간의 정보를 담은 리스트 변수가 하나 필요하다. 또한, 초기 input값 처리 부분을 고려하면 될 것으로 보인다.

 

2. 코드

from collections import deque
import copy

n = int(input())

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

time = [0]* (n+1)

# 방향 그래프의 간선 정보 입력 받기
for i in range(1, n+1):
    data = list(map(int, input().split()))
    time[i] = data[0]
    for x in data[1:-1]:
        indegree[i] += 1
        graph[x].append(i)
"""
5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1
"""

# 위상정렬함수
def topology_sort():
    result = copy.deepcopy(time) # 알고리즘 수행 결과를 담을 리스트
    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] + time[i])
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
    for i in range(1, n+1):
        print(result[i])
topology_sort()

"""
>> 10
   20
   14
   18
   17
"""

3. 코멘트

- 위상정렬 함수의 경우 다시 한번 풀어볼 필요가 있을 것 같다.

- 해당 문제의 경우 기존 진입차수(indegree)뿐만 아니라 시간 또한 다뤄야 했기에 처음에 문제를 이해하는데 시간이 오래 걸렸었다.