문제
- 선수 강의가 있는 경우, 선수 강의를 먼저 들어야 해당 강의를 들을 수 있다.
- 모든 강의는 1번부터 N번까지의 번호를 가진다.
- 동시에 여러 개의 강의를 들을 수 있다.
- N개의 강의를 들을 때 수강하기까지 걸리는 최소 시간은?
풀이
- 전형적인 위상정렬 문제
- 시간 복잡도 : O( V + E ) 이므로 가능하다
- 각 강의에 대해 수강하기까지 걸리는 최소 시간을 각각 구해야 하고, 이는 선수 과목의 최대 시간이 된다.
- 각 강의에 대해 선수과목+현재 강의 시간과 현재 강의 수강하는데 필요한 시간 중 더 큰 값을 넣는다.
from collections import deque
N = int(input())
graph = [[] for _ in range(N+1)]
time = [0] * (N+1)
indegree = [0] * (N+1) # 진입 차수
for i in range(1, N+1):
data = list(map(int, input().split()))
time[i] = data[0]
for pre in data[1:-1]: # 각 선수과목에 대해
indegree[i] += 1 # 진입차수 +1
graph[pre].append(i) # 그래프 연결
result = time[:] # 결과 담을 리스트
q = deque()
# 진입 차수가 0인 노드 삽입
for i in range(1, N+1):
if indegree[i] == 0 :
q.append(i)
# 큐가 빌 때까지 반복
while q:
now = q.popleft()
for i in graph[now]:
# 현재 강의 수강하는데 필요한 시간 VS 선수과목 + 현재 강의 시간
result[i] = max(result[i], result[now]+time[i])
indegree[i] -= 1
if indegree[i] == 0:
q.append(i)
for i in range(1, N+1):
print(result[i])
References
- 이것이 코딩테스트다 ch10 그래프 이론 - 커리큘럼