커리큘럼

출처:: 

분류:: 위상정렬 알고리즘 

 

1. 문제 이해 및 해결과정

 

- 각 노드에 대하여 인접한 노드를 확인 할 때 , 인접한 노드에 대하여 현재보다 강의시간이 더 긴 경우를 찾는다면,  더 오랜 시간이 걸리는 경우의 시간 값을 저장하는 방식으로 결과 테이블을 갱신하여 답을 구할 수 있다.  - 위상 정렬을 수행하면서, 매번 간선 정보를 확인하여 결과 테이블을 갱신한다.

result

 

2. 풀이방법

 1. 위상정렬

#커리큘럼
#
import sys
from collections import deque
import copy
sys.stdin = open("input.txt","r")
'''
5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1

#출력
10
20
14
18
17
'''
n=int(input())

#모든 노드에 대한 진입차수는 0으로 초기화
indegree=[0]*(n+1)
#각 노드에 연결된 간선 정보를 담기 위한 연결리스트 초기화
graph=[[] for _ in range(n+1)]

#각 강의 시간을 0으로 초기화
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]: #맨 뒷 수 전까지 = -1 나오기 전까지
        indegree[i]+=1
        graph[x].append(i)

#위상 정렬 함수
def topology_sort():
    # 리스트를 단순 대입 연산하면 값이 변경되는 문제가 있을 수 있으므로, deepcopy()
    result=copy.deepcopy(time)
    q=deque()

    #진입차수가 0인 노드를 큐에 삽입
    for i in range(1,n+1):
        if indegree[i] ==0:
            q.append(i)

    while q:
        now = q.popleft()
        #해당 원소와 연결된 노드들의 진입차수에서 1빼기
        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()

 

3. 오답원인

 

4. 알게된 점

 deepcopy() 

 : time리스트를 result에 복사하는데 , 단순 대입을 하면 값이 변경될 때 문제가 발생할 수 있으므로, 리스트 값을 복제 시 deepcopy() 이용