[C/C++] 백준 줄 세우기 2252번 / 위상 정렬 알고리즘

백준 2252번 

 

백준 2252번은 위상정렬을 이용해 문제를 풀 수 있습니다.

 

위상정렬이란?

방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬입니다. 

 

 

이런식으로 처음으로 시작하는 정점을 먼저 큐에 놓어준 뒤,   그 정점을 pop 할 때 그 정점과 간선으로 연결된 정점의 indegree값을 빼주는 식으로 코드를 전개하면 됩니다.

 

 

백준 2252번 줄세우기 전체 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N[32001];
vector<int> result;

vector<int> check[32001];

int main() {
	int n, m;

	cin >> n >> m;
	vector<int> vec;
	queue<int> que;


	for (int i = 0; i < m; i++) {
		int A, B;
		cin >> A >> B;
		N[B]++;
		check[A].push_back(B);
	}

	for (int i = 1; i <= n; i++) {
		if (N[i] == 0) que.push(i);
	}

	while (!que.empty()) {
		int cur = que.front(); que.pop();
		cout << cur << " ";


		for (auto nxt : check[cur]) {
			N[nxt]--;

			if (N[nxt] == 0) que.push(nxt);
		}

	}

}