[백준] 2252번 줄세우기 C++ 문제풀이

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

문제 풀이

이 문제는 키의 순서가 정해져있을 때, 차례대로 출력하는 문제이므로 위상 정렬을 이용해야함을 알 수 있다.

1005번 ACM Craft 문제와 유사하지만 여기서는 배열을 출력해야한다는 점만 차이가 있다.

https://itcodeheaven.tistory.com/78

[백준] 1005번 ACM Craft C++ 문제풀이

소스 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> student[32001];
int indegree[32001] = { 0 };

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		student[a].push_back(b);
		indegree[b] += 1;
	}

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0) 
			q.push(i);
	}

	while (!q.empty()) {
		int idx = q.front();
		cout << idx << " ";
		q.pop();

		for (int i = 0; i < student[idx].size(); i++) {
			int dy = student[idx][i];
			indegree[dy] -= 1;
			if (indegree[dy] == 0) {
				q.push(dy);
			}
		}
	}

	return 0;
}