이것이 코딩테스트다 커리큘럼 (Python)

문제 링크

동빈이는 온라인으로 컴퓨터 공학강의를 듣고 있다. 이때 각 온라인 강의는 선수강의가 있을 수 있는데, 선수강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다. 
동빈이는 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번 까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다. 
동빈이가 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오

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

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

---

Test Case

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

출력
10
20
14
18
17

---

문제 풀이

위상정렬 문제.
기본적인 위상정렬 개념과 파이썬의 얕은 복사, 깊은 복사 개념을 알아야 풀 수 있다.
원본 time배열을 복사해서 result배열을 만든뒤 이를 이용해야 하는데 그냥 result = time 이런식으로 해버리면 파이썬에서 배열은 mutable 객체이기때문에 copy.deepcopy를 사용한다.
이걸 모르면 그냥 반복문으로 값복사를 해버리는게 나을 수도 있을 듯.

참고 링크 : https://crackerjacks.tistory.com/14

그리고 list index값에 대해서도 조금 더 편하게 사용할 줄 알아야한다.
data[1:-1] 에서 -1 입력받기 전까지 (라인의 마지막 값) 를 자르기 위해 list[시작:마지막:step] 의 의미가 뭔지 알아야한다.
index 1 부터 -1(끝에서 1번째 원소 이전 원소까지) 라는 의미이고 step은 마지막 값이기때문에 기본값 1.

---

Source Code

import copy
from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n+1)]
indegree = [0] * (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]:
        graph[x].append(i)


def topology_sort():
    q = deque()
    result = copy.deepcopy(time)
    
    # 이런식으로 해도 됨
    # result = []
    # for i in time :
    #     result.append(i)

    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()