Lv.2daggraphtopological-sort
졸업까지 필요한 최소 학기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
새 학과에는 1번부터 n번까지 개의 과목이 있고, 졸업하려면 모든 과목을 들어야 합니다.
일부 과목에는 선수 과목이 있습니다. prereq[i] = [a, b]는 a번 과목을 이수한 다음 학기부터 b번 과목을 들을 수 있다는 뜻입니다.
한 학기에 듣는 과목 수에는 제한이 없지만, 같은 학기에 선수 과목과 그 과목을 함께 들을 수는 없습니다.
모든 과목을 이수하는 데 필요한 최소 학기 수를 반환하세요. 선수 관계가 꼬여 있어 절대 이수할 수 없는 과목이 있다면 -1을 반환합니다.
입출력 예
| n | prereq | result |
|---|---|---|
3 | [[1, 3], [2, 3]] | 2 |
5 | [[1, 2], [2, 3], [1, 4], [4, 5], [3, 5]] | 4 |
3 | [[1, 2], [2, 3], [3, 1]] | -1 |
입출력 예 설명
예 1 — 첫 학기에 1, 2번을, 둘째 학기에 3번을 들으면 됩니다.
예 2 — 1 → 2 → 3 → 5처럼 차례로 들어야 하는 과목이 4개 이어져 있으므로 4학기가 필요합니다. 4번은 2학기나 3학기에 들으면 됩니다.
예 3 — 1, 2, 3번이 서로를 선수 과목으로 요구하므로 아무것도 먼저 들을 수 없습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(n: int, prereq: int[][]) → int
제한 사항
-
n -
prereq.length prereq[i] = [a, b], ,- 같은 쌍
[a, b]는 두 번 이상 주어지지 않습니다.
기대 복잡도
- 시간
- O(N + M)
- 공간
- O(N + M)
입출력 예
| n | prereq | 기대 출력 |
|---|---|---|
3 | [[1,3],[2,3]] | 2 |
5 | [[1,2],[2,3],[1,4],[4,5],[3,5]] | 4 |
3 | [[1,2],[2,3],[3,1]] | -1 |
힌트
힌트
과목을 정점, 선수 관계 a → b를 간선으로 보면 답은 가장 긴 경로에 놓인 정점 수입니다. 사이클이 있으면 -1입니다.
**위상 정렬(Kahn 알고리즘)**을 쓰세요.
- 진입 차수가 0인 과목을 모두 큐에 넣고
term = 1로 둡니다. - 과목
a를 꺼낼 때마다a → b간선을 지우며term[b] = max(term[b], term[a] + 1)로 갱신하고,b의 진입 차수가 0이 되면 큐에 넣습니다. - 큐에서 꺼낸 과목이
n개보다 적으면 사이클이 있는 것입니다.
간선 목록 전체를 "더 이상 바뀌지 않을 때까지" 반복해서 훑는 방식은 긴 사슬에서 이 되어 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1466 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 4 | 판정만 |