위상 정렬는 이름만 보고 판단하면 핵심을 놓치기 쉬운 주제입니다. 이 글은 최신 출처와 구조를 기준으로 독자가 실제로 확인해야 할 기준을 정리합니다.
핵심은 위상 정렬에서 큐와 진입차수가 쓰이는 이유 이해입니다. 단정적인 결론보다 확인 순서와 리스크를 분리해 보는 것이 중요합니다.
위상 정렬 흐름을 그림으로 보기
위상 정렬은 정렬이지만 숫자 정렬이 아니다
위상 정렬은 값을 오름차순으로 정렬하는 알고리즘이 아닙니다. 먼저 해야 하는 일과 나중에 할 수 있는 일을 방향 그래프로 표현한 뒤, 가능한 처리 순서를 만드는 알고리즘입니다.
핵심은 진입차수 0인 노드가 지금 처리해도 되는 노드라는 뜻을 이해하는 것입니다.
선수과목 예시로 보기
예를 들어 자료구조를 듣고 나서 알고리즘을 들을 수 있고, 알고리즘을 듣고 나서 그래프 심화를 들을 수 있다고 해보겠습니다. 이 관계는 방향 그래프로 표현할 수 있습니다.
어떤 과목을 듣기 위해 필요한 선수과목 수가 진입차수입니다. 진입차수가 0이면 지금 바로 들을 수 있는 과목입니다.
조금 더 어려운 예시: 여러 작업이 동시에 가능한 경우
실전 문제에서는 정답 순서가 하나만 나오지 않는 경우가 많습니다. 예를 들어 A와 B가 서로 독립이고, 둘 다 끝난 뒤 C를 할 수 있다면 A를 먼저 해도 되고 B를 먼저 해도 됩니다.
A -> C
B -> C
C -> D
가능한 위상 정렬:
A, B, C, D
B, A, C, D이런 문제에서는 ‘정답이 하나인가’보다 ‘선후관계를 어기지 않는가’가 더 중요합니다. 큐를 쓰면 현재 가능한 후보를 순서대로 꺼낼 뿐이고, 후보가 여러 개면 여러 정답이 자연스럽게 생깁니다.
왜 큐를 쓸까
처리 가능한 노드가 여러 개일 수 있으므로, 그 후보를 담아둘 그릇이 필요합니다. Kahn 알고리즘에서는 이 후보를 큐에 넣습니다. 하나를 꺼내 처리하면 그 노드가 가리키던 다음 노드들의 진입차수를 줄입니다.
vector topologicalSort(int n, vector<vector>& graph) {
vector indegree(n, 0);
for (int u = 0; u < n; u++) {
for (int v : graph[u]) indegree[v]++;
}
queue q;
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) q.push(i);
}
vector order;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : graph[u]) {
if (--indegree[v] == 0) q.push(v);
}
}
return order;
}사이클은 어떻게 알 수 있을까
사이클이 있으면 서로가 서로의 선수조건이 됩니다. 이 경우 어느 노드도 진입차수 0이 되지 않아 큐에 들어오지 못하는 구간이 생깁니다.
알고리즘이 끝났는데 order에 들어간 노드 수가 전체 노드 수보다 적다면, 그래프 안에 사이클이 있다고 판단할 수 있습니다.
A -> B
B -> C
C -> A
모든 노드가 누군가를 기다리므로
진입차수 0인 시작점이 생기지 않는다.언제 위상 정렬을 떠올리면 좋을까
- 문제에 먼저 해야 하는 작업과 나중에 가능한 작업이 나온다
- 선수과목, 빌드 순서, 작업 의존성 같은 표현이 있다
- 방향 그래프로 관계를 만들 수 있다
- 순서가 여러 개일 수 있다
- 사이클이 있으면 불가능 처리해야 한다
정리
위상 정렬은 그래프 문제를 순서 문제로 바꾸는 사고법입니다. 진입차수 0인 노드를 큐에 넣고 하나씩 처리한다는 흐름만 잡으면, 선수과목과 작업 의존성 문제를 훨씬 안정적으로 분류할 수 있습니다.
관련 글로는 그래프 문제는 입력부터 다르다, BFS visited는 큐에 넣을 때 체크해야 할까, 다익스트라에서 우선순위 큐에 같은 노드가 여러 번 들어가도 되는 이유을 함께 보면 좋습니다. 외부 기준은 CP-Algorithms – Topological Sorting, Khan Academy – Topological sort, Wikipedia – Topological sorting을 확인했습니다.
