안녕하세요! 이번 글에서는 위상 정렬에 대해 알아보겠습니다. 위상 정렬은 방향성 비순환 그래프(DAG, Directed Acyclic Graph)에서 정점을 선형으로 나열하는 알고리즘으로, 특정한 순서를 유지해야 할 때 유용합니다. 예를 들어 작업의 종속성을 처리하거나 컴파일러가 코드의 실행 순서를 결정할 때 사용됩니다.
문제 설명
다음 문제를 해결해 보겠습니다.
문제: 작업 스케줄링
여러 개의 작업이 주어졌을 때, 각 작업은 특정한 선행 작업이 필요합니다. 선행 작업이 모두 완료된 후에만 해당 작업을 수행할 수 있습니다. 그래프의 정점은 작업을 나타내고, 간선은 선행 작업을 나타냅니다. 주어진 작업을 가능한 순서로 나열하시오.
입력
첫 번째 줄에는 정점의 개수 N (1 ≤ N ≤ 1000)과 간선의 개수 M (0 ≤ M ≤ 10000)이 주어진다.
다음 M개의 줄에는 x y 쌍이 주어지며, 이는 작업 x가 작업 y보다 먼저 수행되어야 함을 의미한다.
출력
작업을 수행할 수 있는 순서를 한 줄에 공백으로 구분하여 출력한다. 만약 순서가 불가능하다면 -1을 출력한다.
예제 입력
6 6
1 2
1 3
2 4
3 4
4 5
5 6
예제 출력
1 2 3 4 5 6
위상 정렬의 원리
위상 정렬은 두 가지 방법으로 구현할 수 있습니다: DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색). 여기서는 BFS를 이용한 Kahn의 알고리즘을 소개합니다. Kahn의 알고리즘은 다음과 같은 절차로 진행됩니다.
- 모든 정점의 진입 차수를 기록합니다.
- 진입 차수가 0인 정점을 큐에 넣습니다.
- 큐에서 정점을 하나씩 꺼내고, 그 정점을 결과 리스트에 추가합니다.
- 꺼낸 정점으로부터 나가는 모든 간선을 제거하고, 각 간선의 도착 정점의 진입 차수를 업데이트합니다. 진입 차수가 0이 되는 정점을 큐에 추가합니다.
- 큐가 빌 때까지 반복합니다. 결과 리스트의 크기가 입력한 정점의 개수와 다르면 사이클이 존재하는 것이므로
-1을 반환합니다.
기본 코드 구현
아래는 C++로 위상 정렬을 구현한 기본적인 코드입니다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void topologicalSort(int n, vector<vector<int>> &graph) {
vector<int> inDegree(n + 1, 0);
vector<int> result;
// 진입 차수 계산
for (int i = 1; i <= n; i++) {
for (int j : graph[i]) {
inDegree[j]++;
}
}
queue<int> q;
// 진입 차수가 0인 정점 큐에 삽입
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
for (int v : graph[u]) {
inDegree[v]--;
if (inDegree[v] == 0) {
q.push(v);
}
}
}
// 사이클 확인
if (result.size() != n) {
cout << -1 << endl;
} else {
for (int i = 0; i < result.size(); i++) {
cout << result[i] << ' ';
}
cout << endl;
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n + 1);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
graph[x].push_back(y);
}
topologicalSort(n, graph);
return 0;
}
코드 설명
위 코드에서는 먼저 진입 차수를 담기 위해 inDegree라는 배열을 선언합니다. 각 정점의 진입 차수를 계산한 뒤, 진입 차수가 0인 정점을 큐에 넣습니다. 그 다음 큐에서 정점을 꺼내고, 꺼낸 정점으로부터 나가는 간선을 모두 제거하고 진입 차수를 업데이트합니다. 만약 result 리스트의 크기가 정점의 개수와 다르면 사이클이 존재하므로 -1을 출력합니다.
복잡도 분석
위상 정렬의 시간 복잡도는 O(N + M)입니다. 여기서 N은 정점의 개수, M은 간선의 개수입니다. 진입 차수를 세는데 O(M) 시간이 소요되고, 각 정점마다 진입 차수를 업데이트하는 과정에서도 O(M) 시간이 걸립니다. 따라서 전체적으로 O(N + M)의 시간 복잡도를 가집니다. 공간 복잡도는 O(N + M)으로, 그래프를 저장하기 위한 리스트와 진입 차수 배열을 고려해야 합니다.
추가 연습 문제
아래의 추가 연습 문제를 통해 위상 정렬을 더 깊이 이해하고 적용해보세요.
- 주어진 작업을 기반으로 다양한 작업 조합을 만들고 위상 정렬을 적용해 보세요.
- 사이클이 포함된 그래프를 입력으로 주어졌을 때, 적절한 에러 처리를 구현해 보세요.
- 진입 차수가 같은 정점이 여러 개일 경우, 그 중 하나의 정점을 무작위로 선택하도록 구현해 보세요.
결론
이번 포스트에서는 위상 정렬의 개념과 구현 방법, 예제 문제를 통해 위상 정렬의 활용 방법에 대해 배워보았습니다. 위상 정렬은 다양한 분야에서 많이 응용되는 알고리즘이므로 충분히 이해하고 연습하는 것이 중요합니다.
이제 여러분도 위상 정렬을 활용하여 복잡한 작업을 정렬하고 관리하는 데에 자신감을 가질 수 있기를 바랍니다. 계속해서 연습하고 다양한 문제를 풀어보세요!