[백준 2252] 줄 세우기 (C++)

이 문제는 학생들의 키의 대소관계가 주어진다. 따라서, 그래프로 표현이 가능하다. 이때, 키 순서대로 줄을 세운다고 했는데, 그래프에서의 정렬이므로 위상 정렬문제임을 알 수 있다.

위상 정렬은 사이클이 없는 방향 그래프에서 가능하고, 알고리즘은 생각보다 간단하다.

1. 각 정점에서의 진입 차수를 세어 둔다.
2. 진입 차수가 0인 정점들을 큐에 삽입한다.
3. 큐가 빌 때까지 아래의 과정을 반복한다.
   1. 큐에서 정점을 하나 꺼낸다.
   2. 해당 정점에서 방문 가능한 정점들의 진입 차수를 1감소시킨다.
   3. 방문 가능한 정점들 중 진입 차수가 0인 정점들을 큐에 넣는다.

물론, 큐가 아닌 스택 등의 자료구조에 저장해두어도 된다. 이 알고리즘의 시간 복잡도는 한 정점에서 인접 정점을 확인하는 과정을 반복하므로 $O(V + E)$가 된다. 따라서, 주어진 시간 내에 프로그램이 종료됨을 알 수 있다.

이를 코드로 옮기면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int n, m;
int deg[32'001];
vector<int> adj[32'001];
queue<int> q;

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

	cin >> n >> m;
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		adj[u].push_back(v);
		deg[v]++;
	}

	for (int i = 1; i <= n; i++) {
		if (!deg[i]) q.push(i);
	}

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		cout << cur << " ";

		for (int nxt : adj[cur]) {
			deg[nxt]--;
			if (!deg[nxt]) q.push(nxt);
		}
	}
}