BOJ : 2252 줄 세우기

---

[BOJ 2252(G2)리뷰]

N명의 학생들을 키 순서대로 줄 세우려고한다. 이 때 학생들의 키를 알지 못하여 두 학생의 키를 비교한 결과를 통해 정렬하려고 한다. 예를들어, "1번학생이 3번보다 크고 3번학생이 2번보다 크다" 라고 한다면 이 세 학생의 키 순서는 1>3>2 가 될 것이다.

학생들의 정보가 주어졌을때 학생들의 키 순서대로 출력을 해야 한다.

이 문제는 위상정렬이라는 알고리즘을 통하여 해결할 수 있다.

주어진 정보를 그래프로 구성해보자. 만약 "1번학생이 3번보다 크다"라는 정보가 있다면 (1) <- (3)이런식으로 그려보면 된다. 이렇게 모든 정보에 대해 그래프를 그리고 나면 자신을 가리키고 있는 노드의 갯수가 적을 수록 키가 작은 학생임을 알 수 있다.

문제에서 답이 없는 경우에 대한 조건은 주어지지 않았다. 그러므로 모든 학생들간의 관계에 사이클이 없다고 가정하면 차수가 0인 노드가 반드시 1개이상 존재한다. 따라서 차수가 0개인 노드를 큐에넣고 위상정렬을 시작한다. 먼저 Q에 front에 있는 학생을 pop하여 출력하고, 이 학생과 연결되어 있는 노드들의 차수를 하나씩 감소시킨다. 

차수가 감소되어 0이되는 노드가 있다면 이 노드를 다시 큐에 넣고 위 과정을 반복한다. 이렇게하면 결국 초기에 차수가 0인노드부터 시작하여, 계속하여 다른 노드의 차수가 감소되므로, 주어진 정보에 이하여 순서대로 큐에 넣고 빼는 과정을 수행할 수 있다.

/*
	21.01.18
	BOJ : 2252 줄 세우기 (https://www.acmicpc.net/problem/2252)
	위상정렬
*/
#include <bits/stdc++.h>
using namespace std;


int N, M;
int indegree[32001];
vector <int> adj[32001];
queue <int> Q;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;

		adj[a].push_back(b);
		indegree[b]++;
	}

	//indegree가 0인것을 찾음.(사이클 없으므로 가능)
	//어딘가 모아놓음, 모아놓은 것을 하나씩 뽑으면서 출력하고 연결된것들의 간선 제거
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			Q.push(i);
		}
		
	}

	while (!Q.empty()) {
		int cur = Q.front();
		Q.pop();
		printf("%d ", cur);
		for (int i = 0; i < adj[cur].size(); i++) {
			int nxt = adj[cur][i];
			indegree[nxt]--;
			if (indegree[nxt] == 0) {
				Q.push(nxt);
			}
		}
	}

	return 0;
}