<Baekjoon> #1766 문제집, 위상정렬 TopologicalSort c++

문제에서 보면 '먼저 푸는 것이 좋은 문제'가 있다는 말은 문제에 '순서'가 있다는 말이다. 이것은 DFS로 풀 수 있는 가장 유명한 문제중 하나인 위상정렬 (topological Sort)로 푸는 문제이다.

위상정렬 구현 방법

1. 각 정점간의 순서를 저장하며 진입차수 증가
   
   예를 들어 위와같은 그래프가 있을 때

vector<int> adj[MAX];
adj[1].push_back(2); inDegree[2]++;
adj[1].push_back(3); inDegree[3]++;

2. 진입차수 (inDegree)가 0인 수를 queue에 삽입

for (int i=1; i<=n; i++)
	if(inDegree[i]==0) q.push(i);

3. 모든 노드를 방문하며 queue에 있는 정점을 꺼내 그 정점에 이어진 간선을 제거
4. 간선을 제거한 후 진입차수가 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);
        }
}

5. 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;
}