백준 2252(줄 세우기) c++ <위상 정렬>

문제

2252번: 줄 세우기

n명의 사람을 입력받고 m개의 키 순서 정보가 주어집니다.

예를 들어 1 2가 주어지면 1번 보다 2번이 크다는 의미입니다.

키가 작은 순서대로 n명의 사람을 출력하면 됩니다.

만약 키가 비교할 수 없다면 아무거나 출력해주면 됩니다.

 

위 문제는 위상정렬의 기본형 문제입니다.

위상정렬은 각 정점을 우선순위에 따라 배치한것입니다.

일반적으로 위상정렬의 결과는 유일하지 않습니다.

 

1번 정점이 진입 차수가 0이기 때문에 먼저 사라집니다.

즉, 가장 키가 작은 것입니다.

3번 정점이 진입 차수가 가장 낮기 떄문에 먼저 사라집니다.

4번 정점이 진입 차수가 가장 낮기 때문에 먼저 사라집니다.

2번 정점이 진입 차수가 가장 낮기 때문에 먼저 사라집니다.

마지막입니다.

다음과 같이 위상 정렬을 할 수 있습니다.

vector<int>v[32001];
int cnt[32001];

int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
	int a, b;
	cin >> a >> b;
	cnt[b]++;
	v[a].push_back(b);
}

cnt 배열은 해당 정점의 진입 차수를 저장하기 위함입니다.

v벡터는 정점의 위상을 저장해줍니다.

queue<int>q;

for (int i = 1; i <= n; i++)if (cnt[i] == 0)q.push(i);//진입 차수가 0인 정점 큐에 삽입

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

	cout << node << ' ';
	for (int i = 0; i < v[node].size(); i++) {
		int nxt = v[node][i];
		cnt[nxt]--;
		if (cnt[nxt] == 0)q.push(nxt);
	}
}

진입 차수가 낮은 순서대로 정점을 삭제하고 진입 차수를 업데이트하는 과정입니다.

먼저 진입 차수가 0이면 당연히 가장 키가 작으므로 큐에 먼저 모두 넣어줍니다.

while문에 들어가면 현재 큐에 진입차수가 0인 노드 들만 있으므로, 현재 노드에서 연결된 정점의 진입차수를

1씩 낮아지게하고, 진입차수가 0이면 큐에 넣어주면됩니다.

---

전체 코드입니다.

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>

#define INF 2000000000
using namespace std;
using ll = long long;
vector<int>v[32001];
int cnt[32001];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		cnt[b]++;
		v[a].push_back(b);
	}
	queue<int>q;
	for (int i = 1; i <= n; i++)if (cnt[i] == 0)q.push(i);
	while (!q.empty()) {
		int node = q.front();
		q.pop();

		cout << node << ' ';
		for (int i = 0; i < v[node].size(); i++) {
			int nxt = v[node][i];
			cnt[nxt]--;
			if (cnt[nxt] == 0)q.push(nxt);
		}
	}


	return 0;
}