[알고리즘] 위상정렬 교재 문풀

🥕 문제 이름 : 커리큘럼

참고한 책 ; 나동빈 (2020). <이것이 취업을 위한 코딩 테스트다 with 파이썬>. 서울시: 한빛미디어. 303p

 

🍒 문제 분석

N개의 교양 강의를 듣고자 한다. 각 과목에는 선수과목이 있는 과목이 있고 없는 과목이 있다.

강의는 동시에 들을 수 있기 때문에, 가령 과목 3의 선수과목이 1과 2 일 때,

1이 30시간, 2가 20시간 걸린다고 한다면, 과목 3을 듣기 위해 선수과목을 듣는 시간은 30시간이 되는 셈이다.

따라서 강의 3의 강의 시간이 40시간이라면, 과목 3을 수강하기 까지 걸리는 시간은 70 시간이다.

N 개의 강의를 모두 듣는데 걸리는 최소 시간을 구해야 한다.

 

🥑 코드

 

# 입력

5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

 

 

from collections import deque
import copy

N = int(input())                   # 강의 수
indegree = [0] * (N+1)             # 진입 차수
time = [0] * (N+1)                 # 강의 시간
graph = [[] for i in range(N+1)]   # 연결 그래프

for i in range(1, N +1):
    data = list(map(int, input().split()))
    time[i] = data[0]

    for j in data[1:-1]:
        indegree[i] += 1           # 선수 과목 하나 당 진입차수 +1
        graph[j].append(i)         # 선수 과목에다가 하위 과목을 추가한다.

# 위상 정렬 함수
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]:                                   # now의 하위 과목들
            result[i] = max(result[i], result[now]+time[i])    # 과목 i 의 시간 갱신
            indegree[i] -= 1

            if indegree[i] == 0 :
                q.append(i)
        
    for i in range(1, N+1):
        print(result[i])

topology_sort()

• key idea : 선수 과목 중 시간이 더 많이 걸리는 것만 고려해주면 된다. ( 동시 수강이 가능하기 때문 )
• graph[ now ] 에는 과목 now 에 대한 하위 과목들이 담긴다.
• result[i] = max(result[i] , result[now] + time[i]) 을 통해 두가지를 구현할 수 있다.
  1. result[i] 에 아직 선수 과목을 고려하지 않은 하위 과목의 강의 수강 시간이 담겨 있을 경우, 이를 선수 과목을 고려한 강의 시간으로 업데이트 해준다.
  2. result[i] 에 선수 과목을 고려한 강의 수강 시간이 담겨 있지만, 그 값이 now라는 선수 과목을 고려한 수강시간 보다 작을 경우, 과목 now 를 고려한 강의 수강 시간으로 업데이트 해준다. ( key idea 에 적힌 이유로 인해 그렇다. )