Funcia
Lv.2daggraphtopological-sort

졸업까지 필요한 최소 학기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

새 학과에는 1번부터 n번까지 nn개의 과목이 있고, 졸업하려면 모든 과목을 들어야 합니다. 일부 과목에는 선수 과목이 있습니다. prereq[i] = [a, b]는 a번 과목을 이수한 다음 학기부터 b번 과목을 들을 수 있다는 뜻입니다.

한 학기에 듣는 과목 수에는 제한이 없지만, 같은 학기에 선수 과목과 그 과목을 함께 들을 수는 없습니다. 모든 과목을 이수하는 데 필요한 최소 학기 수를 반환하세요. 선수 관계가 꼬여 있어 절대 이수할 수 없는 과목이 있다면 -1을 반환합니다.

입출력 예

nprereqresult
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

제한 사항

  • 1≤1 \le n ≤100,000\le 100{,}000
  • 0≤0 \le prereq.length ≤200,000\le 200{,}000
  • prereq[i] = [a, b], 1≤a,b≤n1 \le a, b \le n, a≠ba \ne b
  • 같은 쌍 [a, b]는 두 번 이상 주어지지 않습니다.

기대 복잡도

시간
O(N + M)
공간
O(N + M)

입출력 예

nprereq기대 출력
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 알고리즘)**을 쓰세요.

  1. 진입 차수가 0인 과목을 모두 큐에 넣고 term = 1로 둡니다.
  2. 과목 a를 꺼낼 때마다 a → b 간선을 지우며 term[b] = max(term[b], term[a] + 1)로 갱신하고, b의 진입 차수가 0이 되면 큐에 넣습니다.
  3. 큐에서 꺼낸 과목이 n개보다 적으면 사이클이 있는 것입니다.

간선 목록 전체를 "더 이상 바뀌지 않을 때까지" 반복해서 훑는 방식은 긴 사슬에서 O(N⋅M)O(N \cdot M)이 되어 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251466 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.