백준 1766 문제집 (c++) : 피너클

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

1766번: 문제집

위상정렬 문제다.

이번에는 priority_queue를 사용하는 위상정렬 알고리즘을 사용한다.

int n, m;
vector<int> adj[32001];
int inDegree[32001];

사용할 변수다. adj는 문제끼리의 순서가 들어가고

inDegree는 해당 문제가 어떤 문제 다음으로 풀려야 하는지를 확인한다.

현재 예제 상태를 그래프로 표현하면 위와 같다. 위를 보며 2와 1에는 간선이 1개 들어가고 있다.

그렇다면 inDegree[2] = 1, inDegree[1] = 1이 되는 것이다. 2개가 들어가면 2가 된다.

cin >> n >> m;
memset(inDegree, 0, sizeof(inDegree));
for (int i = 0; i < m; i++) {
	int a, b;
	cin >> a >> b;
	adj[a].push_back(b);
	inDegree[b]++;
}

메인함수다.

inDegree를 0으로 초기화하고 값들을 입력받는다.

vector<int> ans = topologySort();
for (int i = 0; i < n; i++) cout << ans[i] << ' ';

그후 위상정렬 결과를 ans에 받고 ans를 출력하면 된다.

vector<int> topologySort() {
	vector<int> ans;
	priority_queue<int> pq;
	for (int i = 1; i <= n; i++)
		if (inDegree[i] == 0) pq.push(-i);

위상정렬 변수다. topologySort가 철자가 맞는지는 모르겠다.

ans에는 정답이 담긴다.

priority_queue를 하나 만들고 inDegree[i]가 0인 것만 pq에 담는다.

예제의 경우에는 4와 3이 담길것이다. 넣을때는 우선순위를 위해 -를 붙여준다.

	while (!pq.empty()) {
		int now = -pq.top();
		pq.pop();
		ans.push_back(now);

그후 pq가 비어있지 않은동안 반복한다,

now에 pq.top * -1을 집어넣고 pq.pop을 한뒤 ans에 now를 집어넣는다.

		for (int i = 0; i < adj[now].size(); i++) {
			int next = adj[now][i];
			if (--inDegree[next] == 0) pq.push(-next);
		}
	}

그후 now와 연결된 정점들중 now와의 간선을 끊었을때 가지고 있는 간선이 0이 되는걸 pq에 집어넣는다.

위의 상황에서 현재 now는 3이다. 3와 연결된 정점들의 간선을 끊는다. 여기선 1과 연결된 간선을 끊는다.

이제 1의 간선을 확인한다. 현재 1이 가진 간선의 수는 0이다. 그렇다면 1을 pq에 넣는다.

위의 동작을 pq가 전부 빌때까지 반복하는 것이다.

	return ans;
}

while문이 끝나면 ans를 반환한다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

int n, m;
vector<int> adj[32001];
int inDegree[32001];

vector<int> topologySort() {
	vector<int> ans;
	priority_queue<int> pq;
	for (int i = 1; i <= n; i++)
		if (inDegree[i] == 0) pq.push(-i);

	while (!pq.empty()) {
		int now = -pq.top();
		pq.pop();
		ans.push_back(now);
		for (int i = 0; i < adj[now].size(); i++) {
			int next = adj[now][i];
			if (--inDegree[next] == 0) pq.push(-next);
		}
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	memset(inDegree, 0, sizeof(inDegree));
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		inDegree[b]++;
	}

	vector<int> ans = topologySort();
	for (int i = 0; i < n; i++) cout << ans[i] << ' ';
}

전체코드다.