골드2 - 백준 1766 문제집

백준 1766 문제집

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

접근방법

이 문제는 풀 수 있는 문제 중 가장 쉬운 문제를 풀어나가면서 총 N개의 문제를 전부 푸는 문제였다. 한 문제가 해결되면 풀 수 있는 문제가 늘어나게 되고, 매번 정렬을 새로 해야하기 때문에 우선순위 큐를 써야겠다고 생각했다. 풀 수 있는 문제(선행 문제가 전부 풀린 문제)를 우선순위 큐에 넣어 정렬하고, 우선순위 큐의 제일 위에 있는 문제를 꺼내서 출력해주었다.

풀이

problem 배열을 만들어서 선행되어야 하는 문제의 개수가 몇개인지 저장했고 problem 배열의 값이 0이 되면 선행 문제가 전부 해결됐다고 판단하여 우선순위 큐에 넣어주는 식으로 진행하였다.

우선 problem 배열을 순회하면서 바로 해결 가능한 문제들을 우선순위 큐에 넣어주었고 while문에서 우선순위 큐 제일 위에 있는 문제를 꺼내어 출력했다. 그리고 연결된 문제들의 problem 배열값을 1씩 감소시켜주었다. 이때 값이 0이 되면 우선순위 큐에 해당 문제를 넣어주었다.

코드

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

using namespace std;

priority_queue<int, vector<int>, greater<int>> possible;
vector<vector<int>> pre_solve;
int problem[32001];

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

	int N, M;
	cin >> N >> M;

	for (int i = 0; i <= N; i++)
	{
		vector<int> temp;
		pre_solve.push_back(temp);
	}

	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		pre_solve[a].push_back(b);
		problem[b]++;
	}

	for (int i = 1; i <= N; i++)
	{
		if (problem[i] == 0)
			possible.push(i);
	}

	while (!possible.empty())
	{
		int cur = possible.top();
		possible.pop();
		cout << cur << ' ';

		for (int i = 0; i < pre_solve[cur].size(); i++)
		{
			problem[pre_solve[cur][i]]--;

			if (problem[pre_solve[cur][i]] == 0)
				possible.push(pre_solve[cur][i]);
		}
	}

	return 0;
}