[이코테] 그래프 알고리즘 - 커리큘럼

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

동빈이는 온라인으로 컴퓨터 공학 강의를 듣고 있다. 이 때 각 온라인 강의는 선수 강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다. 동빈이는 총 N개의 강의를 듣고자 한다. 강의는 1번부터 N번까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다고 가정한다. 예를 들어, N = 3일 때, 3번 강의의 선수 강의로 1번과 2번 강의가 이씨고, 1번과 2번 강의는 선수 강의가 없다고 하자. 그리고 각 강의에 대하여 강의 시간이 다음과 같다고 하자.

 

• 1번 강의: 30시간
• 2번 강의: 20시간
• 3번 강의: 40시간

이 경우, 1번 강의를 수강하기까지의 최소 시간은 30시간, 2번 강의를 수강하기까지는 최소 20시간, 3번 강의를 수강하기까지는 최소 70시간이 필요하다. 동빈이가 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지는 걸리는 최소 시간을 출력하는 프로그램을 작성해라.

입력조건

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

출력조건

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

사고과정

• 문제를 구체적으로 잘 파악하지 못해서 오해를 하고 문제풀이에 들어갔다. 위 예시를 들어준 것을 대충 읽고 위 예시로 한다면 90시간이 나오도록 구현하려고 했다..
• 강의를 듣는 데 드는 비용을 간선이 아닌가 고민했다. 또 선수과목 관계를 2차원 인접 리스트에 담을 때 처음에 반대로 담았다가 다시 고쳐 담는 데 시간이 걸렸다. 만약 a가 b의 선수과목이다라는 것은 a -> b가 되고 리스트에 담을 때, graph[a].append(b)가 되야 한다.
• 문제 핵심 아이디어는 각 노드(강의)에 대하여 인접한 노드를 확인하면서 인접한 노드에 대해 현재보다 강의 시간이 더 걸린 경우를 찾는다면, 해당 시간으로 결과 테이블을 갱신시켜주면 된다.
• 처음 time 변수 즉, 강의 개별로 듣는 시간이 담긴 time 리스트와 while문을 돌면서 업데이트 되는 강의 시간 리스트 result를 개별로 운영하는 아이디어를 생각하지 못했다. 이 때 copy 라이브러리의 deepcopy 함수를 처음 사용해보았다.

풀이(스스로 못 푼 풀이)

from collections import deque
import copy

n = int(input())
indegree = [0] * (n+1)
time = [0] * (n+1)
graph = [[] for _ in range(n+1)]
for i in range(1, n+1):
    data = list(map(int, input().split()))
    # 각 과목 수강 시간 기록
    time[i] += data[0]
    # 그래프 데이터 입력
    for d in data[1:-1]:
        graph[d].append(i)  # 선수과목이 d니까 d -> i
        indegree[i] += 1    # 진입차수는 들어오는 노드 입장이므로 i


def topology_sort():
    result = copy.deepcopy(time)
    q = deque()
    # 초기에 진입차수 0인 노드들 큐에 넣기
    for i in range(1, n+1):
        if indegree[i] == 0:
            q.append(i)
    # 큐가 빌 때까지 반복
    while q:
        node = q.popleft()
        for next in graph[node]:
            indegree[next] -= 1
            # max(result에 업데이트된 인접 노드시간, result에 업데이트된 현재노드 시간 + 인접노드의 처음 시간)
            result[next] = max(result[next], result[node] + time[next])
            if indegree[next] == 0:
                q.append(next)

    for i in range(1, n+1):
        print(result[i], end=' ')

topology_sort()