백준 / 1766 문제집 C++

www.acmicpc.net/problem/1766

1766번: 문제집

간단한 위상정렬 문제였습니다. 기본적으로 숫자가 작을 수록 쉬운 문제이고, 먼저 풀어야하는 우선순위가 정해져있을 때 문제를 푸는 순서를 구하는 문제입니다.

 

1번을 먼저 풀고 3번을 풀고, 1번을 먼저 풀고 4번을 풀어야한다고 하면 (1->3, 1->4)

문제 푸는 순서는 1, 3, 4도 되고 1, 4, 3도 되지만, 3 < 4이므로 1, 3, 4가 정답이 되는 그런 문제입니다.

 

먼저 풀어야하는 문제가 있으므로 기본적으로 위상정렬을 이용해 정렬을 하면 되지만, 같은 우선순위의 문제는 수가 작은걸 먼저 풀어야 하므로 그냥 큐가 아닌 우선순위 큐를 이용해 같은 우선순위들을 정렬해주면 됩니다. (오름차순으로)

 

코드는 다음과 같습니다.

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

using namespace std;

int n, m;
vector<int>v[32001]; // v[A] = {B,...} : A가 B보다 반드시 먼저
int degree[32001]; // 들어오는 차수
vector<int>result; // 정렬 결과

void init()
{
	cin >> n >> m;
	memset(degree, 0, sizeof(degree));
	for (int i = 0; i < m; i++) {
		int A, B;
		cin >> A >> B;
		v[A].push_back(B);
		degree[B]++;
	}
}

// 위상 정렬
void topological_sort()
{
	priority_queue<int, vector<int>, greater<int>>q; // 우선순위 같은 문제라도 숫자 작은 거부터 풀어야한다.
	for (int i = 1; i <= n; i++) {
		if (degree[i] == 0)
			q.push(i);
	}

	while (!q.empty()) {
		int node = q.top();
		q.pop();
		result.push_back(node);

		for (int i = 0; i < v[node].size(); i++) {
			int nextnode = v[node][i];
			degree[nextnode]--;
			if (degree[nextnode] == 0)
				q.push(nextnode);
		}
	}
}

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

	init();
	topological_sort();

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << ' ';
}