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

백준 2252 줄 세우기 문제
백준 2252 줄 세우기 소스코드

📄 문제 설명

Problem

N명의 학생들을 키 순서대로 줄을 세우려고 한다.
일부 학생들의 키만을 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

Input

첫째 줄 : N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)
(M은 키를 비교한 회수이다.)
다음 M개의 줄 : 키를 비교한 두 학생의 번호 A, B가 주어진다.
(학생 A가 학생 B의 앞에 서야 한다는 의미 / 학생들 번호는 1번 ~ N번)

Output

첫째 줄에 학생들을 키 순서대로 줄을 세운 결과를 출력
(답이 여러 가지인 경우에는 아무거나 출력)

Example Input 1

3 2
1 3
2 3

Example Output 1

1 2 3

Example Input 2

4 2
4 2
3 1

Example Output 2

4 2 3 1

📝 문제 해설

이 문제는 두 학생의 키를 비교한 m개의 결과를 가지고 키 순서 결과를 출력하는 프로그램이다.

키가 작은 사람 뒤에 키가 큰 사람이 나열되어 한 방향으로 연결이 된다.
따라서 <위상정렬>을 사용해 문제를 해결하였다.

▶ 위상정렬 (Topological Sort)

DAG(Directed Acyclic Graph)에서 그래프의 방향성을 거스르지 않고, 정점들을 나열하는 것
* DAG : 비순환 방향 그래프 (순환을 가지지 않는)

- 위상정렬은 각 정점을 우선순위에 따라 배치한 것.
- 일반적으로 위상정렬의 결과는 유일하지 않다.

1) 진입차수(inDegree) input 받기
2) 진입차수 0인 데이터 Queue에 적재
3) Queue에서 하나씩 뽑으면서 연결된 간선 끊기
	3-1) inDegree --;
	3-2) inDegree 0인 데이터 Queue 적재

** 답이 여러개가 있을 수 있다.

다시 문제로 돌아와서,

진입차수를 저장하는 student라는 vector와 전체 그래프를 저장할 graph라는 벡터 생성 후,
a보다 키가 큰 b의 진입차수를 ++ 해준다. (student[b] ++;) ----- (1)
그 후 진입차수(student)가 0인 데이터를 Queue에 넣어주고 ----- (2)
while문으로 Queue가 비었을 때까지 순회한다.
front에 하나씩 뽑으며 연결되어 있는 간선을 끊는다 ----- (3)
이 때, 연결된 간선의 진입차수도 감소시켜주고 (-- student[graph[front][i]]) ----- (3-1)
진입차수가 0이 되면 Queue에 적재시킨다. ----- (3-2)

</> Source Code

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, m;
	scanf("%d %d", &n, &m);

	vector<int> student;
	vector<vector<int>> graph;

	for (int i = 0; i <= n; i++) {
		student.push_back(0);
		vector<int> a;
		graph.push_back(a);
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);

		student[b] ++;
		graph[a].push_back(b);
	}

	queue<int> q;

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

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

		printf("%d ", front);

		for (int i = 0; i < graph[front].size(); i++) {
			if (--student[graph[front][i]] == 0) {
				q.push(graph[front][i]);
			}
		}
	}
  
	return 0;
}