문제에서 보면 '먼저 푸는 것이 좋은 문제'가 있다는 말은 문제에 '순서'가 있다는 말이다. 이것은 DFS로 풀 수 있는 가장 유명한 문제중 하나인 위상정렬 (topological Sort)로 푸는 문제이다.
- 각 정점간의 순서를 저장하며 진입차수 증가
예를 들어 위와같은 그래프가 있을 때vector<int> adj[MAX]; adj[1].push_back(2); inDegree[2]++; adj[1].push_back(3); inDegree[3]++;
- 진입차수 (inDegree)가 0인 수를 queue에 삽입
for (int i=1; i<=n; i++) if(inDegree[i]==0) q.push(i);
- 모든 노드를 방문하며 queue에 있는 정점을 꺼내 그 정점에 이어진 간선을 제거
- 간선을 제거한 후 진입차수가 0인 수를 queue에 삽입
vector<int>result; while (!q.empty()) { int x=q.front(); q.pop(); result.push(x); for (int i=0; i<adj[x].size(); i++) { int y=adj[x][i]; if (--inDegree[y]==0) q.push(y); } }
- result에 저장된 값을 순서대로 출력하면 위상정렬의 결과
이 문제에서는 1번 문제가 가장 쉽고 N번 문제가 가장 어렵다고 할 때, 쉬운 문제부터 푸는 것도 조건으로 들어가 있기 때문에 min heap을 구현해야 한다. 그부분을 제외하고는 본질적으로 동일하다.
#include<iostream>
#include<vector>
#include<queue>
const int MAX = 32001;
using namespace std;
vector<int> adj[MAX];
priority_queue <int, vector<int>, greater<int>> pq;
vector<int> inDegree;
void makeGraph(int n, int m) {
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
inDegree[b]++;
adj[a].push_back(b);
}
}
void topologicalSort(int n, int m) {
vector<int> result;
for (int i = 1; i <= n; i++)
if (inDegree[i] == 0)
pq.push(i);
while (!pq.empty()) {
int x = pq.top();
pq.pop();
cout << x << " ";
for (int i = 0; i < adj[x].size(); i++) {
int y = adj[x][i];
if (--inDegree[y] == 0) pq.push(y);
}
}
cout << "\n" << endl;
}
int main() {
int n, m;
cin >> n >> m;
inDegree = vector<int>(n+1, 0);
makeGraph(n, m);
topologicalSort(n, m);
return 0;
}