[그래프] - 커리큘럼(위상정렬)

선행 순서가 있는 수업들을 각 입력이 들어올 때마다 해당 입력된 수업의 소비 시간을 구하라.

선행 순서 ==> 위상정렬을 사용해야 함 !

 

 

 

나의코드

n=int(input())

arr=[]
in_count=[]

for i in range(0,n):
    arr.append(list(map(int,input().split())))
    arr[i].pop()
    in_count.append(len(arr[i])-1)


for x in arr:
    if len(x)==1:
        print(x[0])
    else:
        S=x[0]
        for i in range(1,len(x)):
            S=S+arr[x[i]][0]
            print(S)
        print(S)

음.. 위상 정렬을 사용한다는것은 알겠지만.. 

큐를 사용해서 하나씩 로직을 처리하지 못하고 나의 생각다로 코드르 작성하였다.

마지막 입력값 이외에는 모드 출력이 되긴 하지만 출력된 값들은 모두 우연히 위 문제에서 주어진 입력값들만 우연히 출력값이 나오도록 짜맞혀서 코드를 짠것 같다..흠..

결국 풀이를 참고 하였다.

 

 

 

정답코드

from collections import deque
import copy

# 노드의 개수 입력받기
v = int(input())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph = [[] for i in range(v + 1)]
# 각 강의 시간을 0으로 초기화
time = [0] * (v + 1)

# 방향 그래프의 모든 간선 정보를 입력받기
for i in range(1, v + 1):
    data = list(map(int, input().split()))
    time[i] = data[0] # 첫 번째 수는 시간 정보를 담고 있음
    for x in data[1:-1]:
        indegree[i] += 1
        graph[x].append(i)

# 위상 정렬 함수
def topology_sort():
    result = copy.deepcopy(time) # 알고리즘 수행 결과를 담을 리스트
    q = deque() # 큐 기능을 위한 deque 라이브러리 사용

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, v + 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
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)

    # 위상 정렬을 수행한 결과 출력
    for i in range(1, v + 1):
        print(result[i])

topology_sort()

위상정렬 알고리즘의 응용문제이다.

각각의 강의 시간을 저장하는 time리스트와 진입 차수를 나타내는 indgree 리스트, 진입하는 선행 노드(강의) 정보를 저장하는 graph 인접리스트를 사용하는 문제이다.

 

입력 하나하나에 출력 값을 바로 내놓지 않아도 된다..!!

 

각각 time,indree,graph에 대한 정보를 저장한 이후 위상정렬 알고리즘을 수행하며 최종적인 result 리스트를 완성 하는것이다.

(위상정렬 함수에서의 copy.depepcopy(time)은  리스트를 복사 하기 위해 사용 !