위상정렬 (Topological Sort)

관련 문제

문제	난이도	핵심
선입 선출 스케줄링	Lv.4	위상정렬 기본
줄 세우기	Lv.4	위상정렬 응용
작업 순서	Lv.3	DAG 위상정렬

---

1. 개념

위상정렬은 방향 그래프에서 노드들을 의존 관계 순서대로 나열하는 알고리즘이다.

DAG(Directed Acyclic Graph, 방향 비순환 그래프) 에서만 사용할 수 있다.

예시: 과목 이수 순서

수학 → 알고리즘 → 자료구조
              ↘
               컴파일러

수학을 먼저 들어야 알고리즘을 들을 수 있고,
알고리즘을 들어야 자료구조와 컴파일러를 들을 수 있다.

---

2. 동작 과정

진입 차수(In-degree) 기반 BFS (칸 알고리즘)

진입 차수: 해당 노드로 들어오는 간선의 수

1. 모든 노드의 진입 차수 계산
2. 진입 차수가 0인 노드를 큐에 삽입
3. 큐에서 노드를 꺼내 결과에 추가
4. 해당 노드와 연결된 간선 제거 (인접 노드의 진입 차수 -1)
5. 진입 차수가 0이 된 노드를 큐에 삽입
6. 큐가 빌 때까지 반복

단계	큐	처리 노드	결과
초기	[수학]	-	[]
1	[알고리즘]	수학	[수학]
2	[자료구조, 컴파일러]	알고리즘	[수학, 알고리즘]
3	[컴파일러]	자료구조	[수학, 알고리즘, 자료구조]
4	[]	컴파일러	[수학, 알고리즘, 자료구조, 컴파일러]

---

3. 핵심 사용 패턴

진입 차수 계산

indegree[] 배열로 각 노드의 진입 차수를 관리

간선 A → B가 있으면 indegree[B]++
노드를 처리하면 인접 노드의 indegree--
indegree == 0이 되면 큐에 삽입

사이클 감지

위상정렬 결과의 노드 수가 전체 노드 수보다 적으면 사이클이 존재한다는 뜻이다.

결과 노드 수 == 전체 노드 수 → 사이클 없음 ✅
결과 노드 수 < 전체 노드 수  → 사이클 존재 ❌

---

4. 핵심 포인트 2가지

DAG에서만 사용 가능하다

사이클이 있는 그래프에서는 진입 차수가 0이 되는 노드가 존재하지 않아 위상정렬이 완성되지 않는다. 문제에서 순환 의존성이 있으면 위상정렬을 쓸 수 없다.

결과가 유일하지 않을 수 있다

진입 차수가 0인 노드가 여러 개면 어떤 노드를 먼저 처리해도 된다. 따라서 위상정렬 결과는 여러 개일 수 있다. 문제에서 사전순이나 특정 조건을 요구하면 우선순위 큐를 써야 한다.

---

5. 시간복잡도

유형	시간복잡도	비고
위상정렬 (BFS)	O(V + E)	V = 노드 수, E = 간선 수
위상정렬 (DFS)	O(V + E)	역순으로 결과를 쌓음

---

6. 주의사항

• DAG에서만 사용 가능하다. 사이클이 있으면 위상정렬이 완성되지 않는다.
• 진입 차수를 정확히 계산해라. 간선 방향을 잘못 읽으면 진입 차수가 틀린다.
• 결과가 여러 개일 수 있다. 특정 순서를 요구하면 우선순위 큐를 써라.
• 사이클 감지에 활용할 수 있다. 결과 노드 수가 전체 노드 수보다 적으면 사이클이 존재한다.