[이코테] 09. 그래프 이론 - 커리큘럼

---

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다.

---

문제

온라인으로 컴퓨터 공학 강의를 들으려 한다. 이때 각 온라인 강의 중 선수 강의가 있는 강의는 선수 강의를 먼저 들어야 한다. 또한 동시에 여러 개의 강의를 들을 수 있다고 가정한다.

N개의 강의 정보가 주어졌을 때, 각 강의를 수강하기까지 걸리는 최소 시간을 각각 출력하라.

 

입력 조건

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

출력 조건

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

 

입력 예시
5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

출력 예시
10
20
14
18
17

 

 

---

나의 풀이

from collections import deque

N = int(input())
# 진입 차수 초기화
indegree = [0] * (N+1)
# 간선 정보 연결 리스트
graph = [[] for _ in range(N+1)]

time = [0] * (N+1)

# i번 강의 -> 강의 시간, 선수강의번호, -1
for i in range(1, N+1):
    t, *arr = map(int, input().split())
    time[i] = t

    # x번 강의 -> i번 강의
    for x in arr:
        if x == -1:
            break

        graph[x].append(i)
        indegree[i] += 1


# 위상 정렬
def topology():
    # 알고리즘 수행 결과를 담을 리스트
    result = [t for t in time]
    q = deque()

    # 진입차수가 0
    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])

            # now와 연결된 노드 제거
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    print(*result[1:], sep="\n")


topology()

---

해설

위상 정렬 알고리즘의 응용 문제이다.
각 노드에 대하여 인접한 노드를 확인할 때, 인접한 노드에 대하여 현재보다 강의 시간이 더 긴 경우를 찾는다면 그 시간을 저장하는 방식으로 결과 테이블을 갱신하여 답을 구할 수 있다.
따라서 위상 정렬을 수행하면서, 매번 간선 정보를 확인하여 결과 테이블을 갱신한다.

최종 각 강의를 수강하기까지 걸리는 최소 시간을 result 변수에 담고 있다. 또한 처음 각 강의의 시간은 time 변수에 담았는데, 단순히 대입 연산으로 리스트 변수를 복사하면, 값이 변경될 때 문제가 생긴다.
풀이에서는 time의 값을 하나씩 할당하여 리스트를 구성하였으며, 파이썬에서 리스트의 값을 복사할 때 deepcopy() 함수를 사용할 수도 있다.

---