https://www.acmicpc.net/problem/2252
이 문제를 풀기 위해서는 위상 정렬에 대한 이해가 필요하다!
위상 정렬?
위상 정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미하며 정렬 알고리즘의 일종이다. 위 문제와 같이 1은 3보다 먼저 와야하고 2는 3보다 먼저 들어와야 한다는 방향성이 있을 때 사용 가능하는 알고리즘이다. 따라서 위상 정렬의 결과는 1 2 3 혹은 2 1 3 이 된다.
진입차수 & 진출차수
위상 정렬 알고리즘을 알기 위해서는 진입차수와 진출차수를 알아야한다. 진입차수(indegree)는 특정한 노드로 들어오는 간선의 개수를 의미하고 진출차수는(outdegree)는 특정한 노드에서 나가는 간선의 개수를 의미한다. 예제 1의 경우 1의 진입차수는 0, 진출차수 1, 2의 경우는 진입차수 0 진출차수 1, 3의 경우 진입 차수 2 진출 차수 0이 된다. 이때 위상 정렬 알고리즘에서 중요하는 것은 진입 차수이다.
위상정렬 알고리즘
위상 정렬의 알고리즘은 간단하게 2과정으로 진행된다.
1. 진입차수가 0인 노드를 큐에 넣는다.
어떤 노드가 진입 차수가 0이라는 것은 이 노드보다 먼저 들어와야 하는 노드가 없다는 것으로 사실상 1순위가 되는 것이다. 그렇기 때문에 진입차수가 0인 노드를 큐에 넣고 순서대로 pop()을 진행한다.
이때 진입차수가 얼마인지 알기 위해서 배열 second[]에 진입차수를 저장하고 큐에서 노드를 꺼낼 때 그 다음 노드들에 대한 정보가 필요하기 때문에 vector<int> v1[32001]을 정의하여 저장한다.
for(int i=0;i<m;i++){
int tmp1,tmp2;
cin>>tmp1>>tmp2;
second[tmp2]++; //진입차수가 추가!
v1[tmp1].push_back(tmp2);
}
2. 큐가 빌때까지 밑에 과정을 반복한다.
2-1. 큐에서 새로운 노드를 꺼낸다.
큐에서 새로운 노드를 꺼내고 더 이상 진입차수가 0인 정보가 필요없으므로 second[] 값의 -1을 넣어준다.
2-2. 꺼낸 노드와 연결된 노드의 진입차수를 줄이고 그 진입차수가 0이면 큐에 push()한다
말 그래도 pop()한 노드를 꺼내서 그래프에서 없애게 된다면 이 노드와 연결된 노드의 진입차수가 1씩 줄어들게 될 것이다. 이때 위의 1번과 같이 진입차수가 0인노드를 큐에 넣는데, 바뀐 그래프에서 더 이상 이 노드보다 앞선 노드가 없으므로 그래프에서 순서상 1순위가 되기 때문이다.
while(!q1.empty()){
int out=q1.front();
q1.pop();
result.push_back(out);
second[out]=-1;
for(int i=0;i<v1[out].size();i++){
int tmp=v1[out][i];
second[tmp]--;
if(second[tmp]==0)
q1.push(tmp);
}
}
마지막으로 result 배열에 정답들을 저장하여 이 값들을 출력하면 된다.
소스코드!
#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<limits.h>
using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int second[32001];
vector<int> v1[32001];
queue<int> q1;
vector<int> result;
void topological_sort(int n){
while(!q1.empty()){
int out=q1.front();
q1.pop();
result.push_back(out);
second[out]=-1;
for(int i=0;i<v1[out].size();i++){
int tmp=v1[out][i];
second[tmp]--;
if(second[tmp]==0)
q1.push(tmp);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int tmp1,tmp2;
cin>>tmp1>>tmp2;
second[tmp2]++; //진입차수가 추가!
v1[tmp1].push_back(tmp2);
}
for(int i=1;i<=n;i++)
{
if(second[i]==0){
q1.push(i);
second[i]=-1;
}
}
topological_sort(n);
for(int i=0;i<n;i++){
cout<<result[i]<<" ";
}
}
'알고리즘! > Graph' 카테고리의 다른 글
[C/C++] 백준 20040: 사이클 게임 (Union-Find) (0) | 2023.10.12 |
---|---|
[C/C++] 백준 1197: 최소 스패닝 트리 (Kruskal 알고리즘) (1) | 2023.10.10 |
[C/C++] 백준 5639: 이진 검색 트리 (backtrack을 통한 후위순회) (1) | 2023.09.26 |
[C/C++] 백준 2206: 벽 부수고 이동하기 (BFS,tuple 이용 풀이) (0) | 2023.09.18 |
[C/C++] 백준 11725: 트리의 부모 찾기(vector 이용) (0) | 2023.09.17 |