커리큘럼

강의 요약:

이코테 문제이며, 강의간 선수,후수과목이 존재하고 각 과목마다 수강까지의 최소시간이 있을때 수업당 수강까지 걸리는 최소시간을 구하시오.

이코테 난이도 3

 

소요시간:

28분

 

1차시도:

from collections import deque

n = int(input())

indegree = [0]*(n+1)

graph_go = [[] for _ in range(n+1)]
graph_back = [[] for _ in range(n+1)]
cost = [0]*(n+1)

for i in range(1,n+1):
	arr=list(map(int,input().split()))
	#들어야하는 시간은 일단 첫번째 숫자
	cost[i] = arr[0]
	#맨앞은 시간 끝은 -1
	for j in arr[1:-1]:
		graph_go[j].append(i)
		indegree[i]+=1
		graph_back[i].append(j)
		
def topology():
	#indegree가 0인거 먼저 찾기
	q = deque([])
	for i in range(1,n+1):
		if indegree[i]== 0:
			q.append(i)
	while q:
		now = q.popleft()
		#진입차수가 0인 것들 최종 cost계산
		#나한테 오기 직전인것들 중 가장 높은 cost더해주기
		cost[now] += max([cost[j] for j in graph_back[now]]) if graph_back[now]!=[] else 0
		for i in graph_go[now]:
			indegree[i]-=1
			if indegree[i]==0:
				q.append(i)
				
	for i in cost[1:]:
		print(i,end = '\n')
		
topology()

indegree를 이용하여 계산하는 위상정렬 문제이다. 위상정렬 원리는 진입차수가 0 이 되는 순으로 q에 넣고 연결되는 진입차수를 1씩 빼주는 것을 반복하면된다. 특히 이문제는 그렇게 진입차수를 계산하는 과정에서 graph_back이라는 그래프를하나 더 만들어 나에게 연결되어있는 노드들을 미리 입력받은뒤 마지막에 cost를 결정할때 나에게 오는 과정에있는 노드들중 가장 큰것에 원래의 자기것을 더해 최소 시간을 정했다.