줄 세우기 (feat. 백준, 2252번)

줄 세우기
https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, M, chk[32001];
	vector<int> ans[32001];
	cin >> N >> M;
	for (register int n = 1; n <= N; ++n)
		chk[n] = 0;
	for (register int m = 0, a, b; m < M; ++m)
		cin >> a >> b, ++chk[b], ans[a].push_back(b);
	queue<int> q;
	for (register int n = 1; n <= N; ++n)
		if (!chk[n])		q.push(n);
	while (!q.empty()) {
		auto f = q.front(); q.pop();
		cout << f << " ";
		for (auto& t : ans[f]) {
			if (!(--chk[t]))		q.push(t);
		}
	}
	return 0;
}
// *&)*@*

1. 1 < 3, 2 < 3 이라는 입력에서 1과 2는 3보다 먼저 체크되어야 합니다.
2. 따라서 a < b 일때, b가 입력된 횟수를 갖고 그 횟수보다 작은 a를 선행하여 출력하는 형태입니다.
3. 단, a의 횟수는 0이 되었을때 출력되어야 합니다. (횟수가 0이 아니라는 것은 이전에 체크해야 하는 번호가 존재한다는 의미이기 때문입니다.)