철수는 온라인으로 컴퓨터공학강의를 듣고 있다. 이때 각 온라인강의는 선수강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저. 들어야만 해당강의를 들을 수 있다. 예를들어 '알고리즘’ 강의의 선수 강의로 '자료구조'가 존재한다면, ‘자료구조를 들은 이후에 ‘알고리즘' 강의를 들을 수 있다. 철수는 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다고 가정한다. 철수가 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오.
입력
첫째줄에 철수가 듣고자 하는 강의의 수 N(1≤N≤500)이 주어진다. 다음 N개의 줄에는 각 강의의 강의 시간과 그 강의를 듣기 위해 먼저 들어야하는 강의들의 번호가 자연수로 주어지며, 각. 이때 강의시간은 100,000이하의 자연수이다 .각 강의번호는 1부터 N까지로 구성되며. 각줄은 -1로 끝난다.
5 10 -1 10 1 -1 4 1 -1 4 3 1 -1 3 3 -1
출력
10 20 14 18 17
✅ 해설
과목 시간과 선수 과목 입력받기
수강 시간은 따로 수강 시간 테이블에 저장
한 줄에 수강 시간과 -1을 제외하고 숫자가 몇 번 입력되는지 세서 진입 차수에 저장
새로운 배열에 선수 과목 저장
# 과목 시간과 선수 과목 입력받기
for subject in range(1, n+1):
data = list(map(int, input().split()))
# 수강 시간 저장
time[subject] = data[0]
for i in data[1:-1]:
# 진입 차수 저장
indegree[subject] += 1
# 선수 과목 저장
graph[i].append(subject)
앞선 선수 과목을 모두 들어야만 다음 과목을 들을 수 있으며, 여러 과목을 동시에 들을 수 있다는 뜻은 그래프 경로 중에서 더 큰 값을 선택하는 것과 같다.
만약 과목 a의 선수 과목 b, c가 존재하고, b, c의 수강시간이 각 10시간, 20시간일 때,
max(b 시간, c 시간) = 20. 최소 20시간 후에 과목 a를 수강할 수 있기 때문이다.
💻 코드
# 강의 n개 입력받기
import copy
n = int(input())
# 진입차수를 저장하는 배열
indegree = [0] * (n+1)
# 수강 시간을 저장하는 배열
time = [0] * (n+1)
# 커리큘럼의 관계를 그래프 형태로 저장
graph = [[] for _ in range(n+1)]
# 과목 시간과 선수 과목 입력받기
for subject in range(1, n+1):
data = list(map(int, input().split()))
# 수강 시간 저장
time[subject] = data[0]
for i in data[1:-1]:
# 진입 차수 저장
indegree[subject] += 1
# 선수 과목 저장
graph[i].append(subject)
# 위상 정렬
def topological():
# 결과
result = copy.deepcopy(time)
queue = []
# 진입차수가 0이면 큐에 삽입
for i in range(1, n+1):
if indegree[i] == 0:
queue.append(i)
# 큐가 빌 때까지 반복
while queue:
now = queue.pop()
for node in graph[now]:
# 더 큰 값을 선택해야 모든 선수과목을 수강하고 다음 과목 수강 가능
result[node] = max(result[node], result[now] + time[node])
# 진입차수 1 줄이기
indegree[node] -= 1
# 만약 진입차수가 0이면 큐에 삽입
if indegree[node] == 0:
queue.append(node)
print(result)
topological()
