[이코테] CH10 그래프 이론 실전문제 4번 커리큘럼

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
def topologysort(index):
   q = deque()
   for i in range(N):
      if indegree2[i] == 0:
         q.append(i) # 문제 없음 , 처음엔 1이 큐에 기본적으로 들어가서 시작하겠지
   while q:
      now = q.popleft()
      for i in graph[now]:
         if indegree2[i] > 0:
          indegree2[i] -=1
         if indegree2[i] == 0:
            q.append(i)
            time2[i] += time2[now]
   return time2[index]

N = int(input())
graph = [[] for _ in range(N+1)] # 이차원 그래프 저장
indegree = [0] * (N+1) # 진입 차수
time = [0] *(N+1) # 노드별 소요 시간
for i in range(1,N+1):
    arr = list(map(int,sys.stdin.readline().split()))
    time[i] = arr[0] # time[i] = arr[0] 
    time2 = copy.deepcopy(time)
    for j in range(1,len(arr)-1):
     graph[arr[j]].append(i) # i -> arr[j]로 이동 가능
     indegree[i] +=1 # i번째로 접근하는게 늘어난다
    indegree2 = copy.deepcopy(indegree)
    print(topologysort(i))
    print(graph,indegree2,time2)

일단 크게 graph, indegree , time 3가지 배열 사용했다

indegree는 진입 차수 , time은 각 노드에 대한 진입 시간

arr[0]이 각 강의에 대한 수강시간을 나타내므로 time[i] = arr[0]

그리고 time배열이랑 indegree 배열 모두 보존이 필요했으므로 deepcopy를 사용했다

 

중요한 것은 ! deepcopy를 사용하지 않고 time2 = time 해버리면 메모리를 참조하는 주소가 똑같아서 배열을 보존할수가 없다

 

출력 형식은 크게 맞추진 않았는데

여기서 출력 형식만 좀 바꾸면 될 것 같다

 

혼자 풀어서 뿌듯했다

그래도 아직 위상정렬 크루스칼 알고리즘이 손에 썩 잘 익지는 않는다

더 문제 풀어보고

기본 코드 복습 한번 더 해야겠다