백준 Gold 2 문제집

문제집 (백준 Gold 2)

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

주어지는 문제집을 효율좋게 푸는 문제

• 문제집은 난이도 순서대로 총 n개 주어짐
  

• 먼저 푸는게 효율적인 정보가 m가 주어지며
  먼저 푸는게 좋은 문제가 있는 문제는
  반드시 그 문제를 풀고 올 것
  

• 먼저 풀만한 문제가 없는 경우
  가능한 쉬운 문제부터 풀을 것
  

풀이 방법

위상정렬 문제이나
입력 차수가 0이여도 ‘문제의 난이도’에 따라
정렬이 필요한 문제

그렇기에 일반적인 queue 대신
우선순위 큐를 사용하여 문제를 풀 수 있다

제출 코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct node
{
	int idx;
	int degree;
	vector<int> next;
};

struct Compare
{
	bool operator()(const node& a, const node& b)
	{
		if (a.degree == b.degree)
			return a.idx > b.idx;

		return a.degree < b.degree;
	}
};

int n, m;

void Topo(vector<node>& nVec)
{
	priority_queue<node, vector<node>, Compare> pq;
	for (node& n : nVec)
	{
		if (n.degree == 0)
			pq.push(n);
	}

	while (pq.empty() == false)
	{
		node n = pq.top();
		pq.pop();

		cout << n.idx + 1 << ' ';

		for (int next : n.next)
		{
			nVec[next].degree--;
			if (nVec[next].degree == 0)
				pq.push(nVec[next]);
		}
	}
}

int main()
{
	cin >> n >> m;

	vector<node> nVec(n);
	for (int i = 0; i < n; i++)
	{
		nVec[i].idx = i;
		nVec[i].degree = 0;
	}

	for (int i = 0; i < m; i++)
	{
		int s, t;
		cin >> s >> t;
		s--;
		t--;
		nVec[s].next.push_back(t);
		nVec[t].degree++;
	}

	Topo(nVec);

	return 0;
}

결과

사실 degree가 0일때만 pq에 넣기 때문에
degree 관련 부분은 Compare 부분에서 적용하지 않아도 되지 않았을까 싶다