문제 출처
- 이것이 취업을 위한 코딩테스트다 with 파이썬
- Chapter 10 - 실전문제 4. 커리큘럼
제한
- 시간 제한 : 2 초
- 메모리 제한 : 128 MB
문제
- 동빈이는 온라인으로 컴퓨터공학 강의를 듣고 있다. 이때 각 온라인 강의는 선수 강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다. 예를 들어 ‘알고리즘’강의의 선수 강의로 ‘자료구조’와 ‘컴퓨터 기초’가 존재한다면, ‘자료구조’와 ‘컴퓨터 기초’를 모두 들은 이후에 ‘알고리즘’ 강의를 들을 수 있다.
- 동빈이는 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다고 가정한다.
- 동빈이가 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 각각 출력하는 프로그램을 작성하시오.
입력
- 첫째 줄에 동빈이가 듣고자 하는 강의의 수 N(1 <= N <= 500)이 주어진다.
- 다음 N개의 줄에는 각 강의의 강의 시간과 그 강의를 듣기 위해 먼저 들어야 하는 강의들이 번호가 자연수로 주어지며, 각 자연수는 공백으로 구분한다. 이때 강의 시간은 100,000 이하의 자연수이다.
- 각 강의 번호는 1부터 N까지로 구성되며, 각 줄은 -1로 끝난다.
출력
- N개의 강의에 대하여 수강하기까지 걸리는 최소 시간을 한 줄에 하나씩 출력한다.
👀 풀이
- 위상정렬 응용 문제이다.
- 차수를 하나씩 벗겨가면서 마지막 강의까지 가면 되는데, 지금 강의와 다음 강의를 들었을 때 누적 시간을 구하면서 가야 한다.
- 이를 위해 각 강의별 최소 시간을 저장할 리스트를 만든 뒤 위상 정렬을 수행하면서 이 리스트를 갱신한다.
코드
