커리큘럼(파이썬) / 위상 정렬(topology sort)

문제

• 온라인 컴퓨공학강의를 듣고 있다.
• 이 때, 각 온라인 강의는 선수강의가 있을 수 있다.
• 1번부터 N번 까지 강의가 주어지고 그에 따른 선수강의가 있을 경우, 각 강의를 듣는데 걸리는 시간을 모두 출력하라.

 

입력

• 첫째 줄에 동빈이가 듣고자 하는 강의 수 N이 주어진다(1<= N <= 500)
• 다음 N개의 줄에는 각 강의의 강의 시간과 그 강의를 드기 위해 먼저 들어야하는 강의들의 번호가 자연수로 주어지며, 각 자연수는 공백으로 구분한다. 이 때 강의 시간은 100,000 이하의 자연수이다.
• 각 강의 번호는 1~N이며 각 줄은 -1로 끝난다.

 

출력

• N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 한 줄에 하나씩 출력한다.

 

"INPUT"
5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

"OUTPUT"
10
20
14
18
17

---

풀이

• 대표적인 위상정렬 문제이다.
• 그래프를 구성하여 진입차수를 정리하고
• 진입 차수가 0 인 접근 가능한 값들에 대해서 차례로 접근하여 값을 갱신한다.

(이 때, 위상정렬 알고리즘 구성 시 q를 통해 차례로 위상정렬을 수행한다)

 

 

실수한 부분

• 선수 과목에서 i를 가르켜야 한다(위상정렬 그래프 방향성은 선수과목 -> 수강과목 순)
• 값 누적집계 처리 시 지금 강의 시간 + 새롭게 추가 vs 누적 강의 시간 중 큰 값으로 갱신(더 큰 시간으로 갱신해야 함)

import sys
from collections import deque
import copy

sys.stdin = open("input/input_10-4.txt" ,"r")
sys.stdout = open("output/ouput_10-4.txt", "w")

# variable
n = int(input())
time = [0] * (n+1)
indegree = [0] * (n+1)
graph = [[] for _ in range(n+1)]

# input
for i in range(1, n+1):
    input_list = list(map(int, input().split()))
    time[i] = input_list[0]
    for prev in input_list[1:-1]:
        indegree[i] +=1
        graph[prev ].append(i) # 선수 과목에서 i를 가르켜야함

# 탐색
def topology_sort():
    # deepcopy 초기값 옮겨가고 time list도 그대로 써야함
    answer = copy.deepcopy(time)
    q = deque()

    # 차수 0 인 노드들 추가
    for i in range(1,n+1):
        if indegree[i] == 0:
            q.append(i)

    # q 빌때까지 반복처리
    while q:
        node = q.popleft()

        # 현재 노드와 연결된 노드들 처리
        for c_node in graph[node]:
            indegree[c_node] -=1
            # 지금까지 들은 강의시간 + 새롭게 강의 듣기 vs i의 원래 누적 강의 시간
            answer[c_node] = max(answer[c_node], answer[node] + time[c_node])

            # 차수 0 이 되었을 경우 추가
            if indegree[c_node] == 0:
                q.append(c_node)

    print(answer[1:])

topology_sort()

---

잘못된 풀이

예를 들어 3번 과목이 2-> 0 -> 3 일 경우 다시 0을 파싱하지 않아서 무한루프를 돈다. 

import sys
from collections import deque

sys.stdin = open("input/input_10-4.txt" ,"r")
sys.stdout = open("ouput_10-2.txt", "w")

# input
n = int(input())
answer = [0] * (n)
prev_list = []
visit = []

# main
for i in range(n):
    str_input = list(input().split())
    answer[i] += int(str_input[0])
    input_q = deque()
    for input_value in list(map(int, str_input[1:-1])):
        input_q.append(input_value-1)
    prev_list.append(input_q)


# 탐색
while True:
    # 체크 완료
    if len(visit) == n:
        break

    # 갈 수 있는 것들 가기
    for i in range(n):
        print('i: ', i, 'visit: ', visit)
        print(prev_list)
        # 위상 0 , 가지 않은 것들
        if len(prev_list[i]) == 0 and i not in  visit:
            visit.append(i) # 방문

            # i 에서 갈 수 있는 것들 제거
            for j in range(n):
                if len(prev_list[j]) == 0:
                    continue

                # 처음 선수과목 i 이면
                elif prev_list[j][0] == i:
                    answer[j] += answer[i]
                    prev_list[j].popleft()
...