[이코테] 그래프 이론_커리큘럼 (python)

문제

나의 풀이

1.

# 강의들 간 방향이 존재하고, 그 방향을 거스르지 않도록 순서대로 나열해야 한다.
# 즉 위상 정렬 알고리즘을 사용

from collections import deque

n = int(input()) # n: 강의(노드) 개수
indegree = [0] * (n + 1) # 모든 노드에 대한 진입차수를 0으로 초기화
# 각 강의(노드)에 연결된 간선 정보를 담기 위한 연결 list 초기화
graph = [[] for _ in range(n + 1)]
time = [0] * (n + 1) # 특정 강의의 수강 시간 list를 모두 0으로 초기화

# 방향 그래프와 모든 간선 정보를 입력받기
for i in range(1, n + 1):
	a, *b, c = map(int, input().split()) # a: 강의 시간, b ~: 선수 강의, c: -1
	time[i] = a # i번 강의의 강의 시간 저장
    
	for j in b:
		graph[j].append(i) # j번 강의의 다음 강의로 i번 강의 저장
        
	indegree[i] += len(b) # i번 강의의 진입차수로 b의 개수만큼 증가
	
# 위상 정렬 함수
def topology_sort():
	sum_time = time[:] # 특정 강의를 수강하기까지의 최소 수강 시간 list
	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]:
			'''
			그 다음 강의를 수강하기까지의 최소 시간
			= 지금까지 계산된 시간과
			현재 강의를 수강하기까지의 최소 시간 + 그 다음 강의의 수강 시간 중 max 값
			가장 큰 값을 고르는 이유는, 그래야 더 적은 시간이 걸리는 선수 강의도 포괄하기 때문
			'''
			sum_time[i] = max(sum_time[i], sum_time[now] + time[i])
			indegree[i] -= 1
		
			# 새롭게 진입차수 = 0이 된 노드를 큐에 삽입
			if indegree[i] == 0:
				q.append(i)
                
	for i in range(1, n + 1):
		print(sum_time[i])
        
topology_sort()

• 깊은 복사:
  : 그냥 b = a를 해버리면, 얕은 복사가 되어버리고 만다.

  • 얕은 복사란? 주소값이 동일! 그래서 만약 list를 복사할 경우, 복사본을 수정하면 Mutable한 list의 특성때문에 원본도 수정되어 버린다.

  • 깊은 복사란? https://crackerjacks.tistory.com/14

    : deepcopy가 가장 느리지만.. 가장 편리한것 같기도 하고? 몇몇 깊은 복사들은 list 내부 사정에 따라 얕은 복사가 되어버리기도 함. 그냥 for문 쓰는게 편한 것 같기도 하고..?
    : 여튼 이 부분은 python 문법 조각에 별도로 저장해야겠다!