파란색가운의 개발 블로그
[이코테] 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 해버리면 메모리를 참조하는 주소가 똑같아서 배열을 보존할수가 없다
출력 형식은 크게 맞추진 않았는데
여기서 출력 형식만 좀 바꾸면 될 것 같다
혼자 풀어서 뿌듯했다
그래도 아직 위상정렬 크루스칼 알고리즘이 손에 썩 잘 익지는 않는다
더 문제 풀어보고
기본 코드 복습 한번 더 해야겠다
'알고리즘 문제 풀이 > 이코테' 카테고리의 다른 글
[이코테] CH10 그래프 이론 실전문제 42번 탑승구 (0) | 2024.01.24 |
---|---|
[이코테] CH10 그래프 이론 실전문제 41번 여행 계획 (0) | 2024.01.22 |
[이코테] CH10 그래프 이론 실전문제 3번 도시 분할 계획 (0) | 2024.01.19 |
[이코테] CH10 그래프 이론 실전문제 2번 팀 결성 (0) | 2024.01.19 |
[이코테] CH10 그래프 이론 크루스칼 알고리즘 기본 코드 (0) | 2024.01.19 |