[백준] 줄 세우기 (2252번)

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

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

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄부터 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1 복사

3 2 1 3 2 3

예제 출력 1 복사

1 2 3

---

 

위상 정렬 문제다.

입력을 받으며 연결된 노드가 몇번인지 벡터에 기록하고, 연결된 노드의 위상을 1 증가한다.

위상은 deg 배열에 기록되는 값으로 해당 노드에 접근하기 전에 먼저 접근해야 하는 노드의 수를 뜻한다.

예를 들어 1 - 2 - 3이라면 위상 deg 배열은 0, 1, 1 일 것이다.

1 - 3, 2 - 3 이렇게 연결되어 있다면 deg 배열은 0, 0, 2 일 것이다. 

 

이렇게 입력을 다 받으면, bfs를 돌리며 노드를 출력한다.

deg가 0인 노드는 바로 출력이 가능하고, 그렇지 않은 노드들은 0인 노드들을 방문하며 삭제를 해서 0이 되면 방문한다.

예를들어 1 - 2 - 3 이라면 위상이 0인 1을 먼저 출력하고 1과 연결된 2의 위상을 1 감소한다. 

그럼 위상이 0이 된 2번 노드를 출력하고 2번과 연결된 3번 노드의 위상을 감소한다. 3번 노드의 위상이 0이 되었으므로 3을 출력하면 끝이나게 된다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%A4%84%20%EC%84%B8%EC%9A%B0%EA%B8%B0%20(2252%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

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

int N, M;
vector<int> v[32001];
int deg[32001];

void bfs() {
	queue<int> q;
	for (int i = 1; i <= N; i++)
		if (deg[i] == 0) q.push(i);

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

		cout << x << " ";

		for (int i = 0; i < v[x].size(); i++) {
			int nx = v[x][i];
			if (--deg[nx] == 0)
				q.push(nx);
		}
	}
}

int main()
{
	cin >> N >> M;
	for (int a, b, i = 1; i <= M; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		deg[b]++;
	}

	bfs();
}