문제 설명
여러 개의 빌딩이 하나의 도시를 구성하고 있습니다. 각 빌딩은 고유한 번호를 가지고 있으며,
빌딩들 사이에는 방향성이 있는 도로가 존재합니다. 문제는 이러한 빌딩들을 특정한 순서로
건축해야 하는 규칙이 존재하며, 그 순서를 구하는 것입니다.
모든 빌딩은 주어진 조건에 의해 건축 순서가 결정됩니다. 이 문제는 위상 정렬(Topological Sort) 문제로
나타낼 수 있습니다. 주어진 규칙을 기반으로 원하는 빌딩의 순서를 계산하여 출력하는 것이
목적입니다.
입력 형식
첫 번째 줄에는 빌딩의 수 N과 도로의 수 M이 주어집니다. (1 ≤ N ≤ 10^6, 0 ≤ M ≤ 10^6)
다음 M개의 줄에는 도로의 정보가 주어지며, 두 정수 A, B가 주어질 경우 이는 빌딩 A가
빌딩 B보다 먼저 건축되어야 함을 의미합니다.
출력 형식
빌딩의 건축 순서를 한 줄로 출력합니다. 만약 건축 순서를 정할 수 없는 경우 ‘0’을 출력합니다.
예제
입력
4 2
1 2
2 3
출력
1 2 3 4
접근 방법
이 문제를 해결하기 위해 우리는 두 가지 방법을 고려할 수 있습니다.
1. DFS(Depth-First Search)를 활용한 방법
2. Kahn의 알고리즘을 활용한 방법
위상 정렬 문제는 사이클이 없는 방향 그래프에서 가능한 빌딩 순서를 찾아야 하는 문제입니다.
여기서 사이클이 존재하면 문제의 요구사항을 만족할 수 없기 때문에,
이를 체크하는 과정이 필요합니다.
1. DFS를 활용한 방법
DFS를 사용하여 그래프를 탐색하면서 각 노드를 방문하는 방식으로
위상 정렬을 수행할 수 있습니다. 이 방식의 핵심은 각 노드를 스택에
추가할 때, 해당 노드의 모든 자식 노드가 방문되었을 때입니다.
2. Kahn의 알고리즘
Kahn의 알고리즘은 각 노드의 진입 차수를 사용하여 위상 정렬을 수행하는 방법입니다.
이 알고리즘은 다음과 같은 단계를 포함합니다:
- 그래프의 진입 차수를 계산합니다.
- 진입 차수가 0인 노드를 큐에 추가합니다.
- 큐에서 노드를 하나씩 꺼내어 출력하고, 해당 노드와 연결된 모든 노드의
진입 차수를 감소시킵니다. 만약 진입 차수가 0이 된 노드를 큐에 추가합니다. - 이 과정을 반복합니다. 모든 노드를 방문했다면 성공적으로 위상 정렬을
수행한 것이고, 사이클이 없는 것입니다.
구현
이제 위에 설명한 Kahn의 알고리즘을 사용하여 문제를 해결하는 코드를
구현해보겠습니다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void topologicalSort(int N, vector>& graph, vector& inDegree) {
queue q;
vector result;
// 진입 차수가 0인 노드를 큐에 추가
for (int i = 1; i <= N; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int current = q.front();
q.pop();
result.push_back(current);
// 현재 노드와 연결된 모든 노드의 진입 차수 감소
for (int neighbor : graph[current]) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
q.push(neighbor);
}
}
}
// 결과 출력
if (result.size() == N) {
for (int i = 0; i < result.size(); i++) {
cout << result[i] << " ";
}
cout << endl;
} else {
cout << "0" << endl; // 사이클이 존재할 경우
}
}
int main() {
int N, M;
cin >> N >> M;
vector> graph(N + 1);
vector inDegree(N + 1, 0);
for (int i = 0; i < M; i++) {
int A, B;
cin >> A >> B; // A -> B
graph[A].push_back(B);
inDegree[B]++;
}
topologicalSort(N, graph, inDegree);
return 0;
}
결론
위상 정렬 문제는 많은 알고리즘 문제에서 접할 수 있는 유형 중 하나로,
특히 프로젝트의 작업 순서를 결정해야 할 때 유용하게 사용될 수 있습니다.
이 강좌에서는 Kahn의 알고리즘을 통해 빌딩 순서를 구하는 문제를 해결했습니다.
다양한 변형 문제가 존재하므로, 실제 코딩테스트에서 실력을 쌓기 위해
다양한 문제를 풀어보기를 권장합니다.
수고하셨습니다! 여러분의 코딩테스트 준비에 많은 도움이 되었기를 바랍니다.