103. 위상정렬(그래프 정렬) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★☆☆

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, a, b, x = 0;
	cin >> n >> m;
	
	vector<int> Degree(n+1, 0);
	vector<int> Work[n+1];
	queue<int> Q;
	
	for(int i = 1; i <= n; i++)
	{
		cin >> a >> b;
		Work[a].push_back(b);
	}
	
	for(int i = 1; i <= n; i++)
	{
		if(Work[i].empty()) continue;
		
		for(int j = 0; j < Work[i].size(); j++)
		{
			Degree[Work[i][j]]++;
		}
	}
	
	for(int i = 1; i <= n; i++)
	{
		if(Degree[i] == 0)
			Q.push(i);
	}
	
	while(!Q.empty())
	{
		int temp = Q.front();
		Q.pop();
		
		cout << temp << " ";
		
		for(int i = 0; i < Work[temp].size(); i++)
		{
			Degree[Work[temp][i]]--;
			if(Degree[Work[temp][i]] == 0)
				Q.push(Work[temp][i]);
		}
	}
	
	return 0;
	
	
}

1. 위상정렬을 할 때는 그래프 정렬을 사용하는데, 할 일의 순서를 정렬해서 출력하는 문제이다.

2. 어떤 한 노드에서 다른 노드로 가는 간선을 진입차수라고 하는데, 이 진입차수의 개수에 따라서 할 일의 순서가 정해진다.

 

vector<int> Degree(n+1)

0

1

2

2

1

0

위 그림에서 각 노드가 가지는 진입차수의 개수를 1차원 벡터 Degree에 정리한 것이다. 해당 배열의 원소가 0이 되면 해야할 일로 판단하고 queue에 push 한다. 최초로는 1과 6이 들어간다.

출력 : 1

queue에서 front인 1을 temp에 할당하고 pop. pop을 했다는 것은 그 일을 했다는 의미이다. 그렇기 때문에 temp를 출력한다.

 

노드 1에서 갈 수 있는 노드는 4이다. 1번 일을 한 후 4번 일을 한다는 의미이다. 그렇기에 Degree[4]-- 를 해준다. 그 후 Degree[4]가 0이라면 해야할 일로 판단하고 queue에 push한다. Degree[4]-- = 1 이므로 패스.

 

출력 : 1 6

노드 6에서 갈 수 있는 노드는 2이다. Degree[2]-- 를 하면 Degree[2] = 0 이 된다. 이 때 Q.push(2) 를 한다.

 

출력 : 1 6 2

노드 2에서 갈 수 있는 노드는 5와 3이다. Degree[5]--, Degree[3]-- 를 하면 Degree[5] = 0 이 된다. 다시 Q.push(5)를 한다.

출력 : 1 6 2 5

노드 5에서 갈 수 있는 노드는 4이다. Degree[4]--를 하면 Degree[4] = 0 이 된다. 다시 Q.push(4)를 한다.

출력 : 1 6 2 5 4

노드 4에서 갈 수 있는 노드는 3이다. Degree[3]--를 하면 Degree[3] = 0 이 된다. 다시 Q.push(3)를 한다.

출력 : 1 6 2 5 4 3

노드 3에서 갈 수 있는 노드는 없다. queue가 empty가 되면서 while문이 break 된다.