[C++] 백준 1766 문제집

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

using namespace std;

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

	priority_queue<int, vector<int>, greater<int>> pq;
	vector<int> x[32001];
	int counting[32001]{0};
	int n, m;

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int left, right;
		cin >> left >> right;
		counting[right]++;	//right의 앞에 가야될 수의 개수
		x[left].push_back(right);
	}

	for (int i = 1; i <= n; i++)
	{
		if (counting[i] == 0)	//right의 앞에 가야되는 수가 없는 경우
			pq.push(i);	//우선순위큐에 수가 작은 순으로 넣는다.
	}

	while(!pq.empty())
	{
		int node = pq.top();	//우선순위의 수
		pq.pop();

		cout << node << " ";

		for (int i = 0; i < x[node].size(); i++)	//그 수보다 뒤에 가게되는 수 검색
		{
			int nextNode = x[node][i];	//그 수보다 뒤에 가게되는 수의 값
			counting[nextNode] -= 1;	//그 값이 1이면 0이되어서 우선순위에 놓고 1이상일때는 1개뺀다.
//그 값이 2이상일 경우는 그 수보다 더 우선순위로 가게되는 수가 더 있기에 그거먼저 처리

			if (counting[nextNode] == 0)	//더 이상 먼저 가게될 수가 없으면 나중순위를 넣는다.
			{
				pq.push(nextNode);
			}
		}
	}
	
}

풀이

1. 먼저 풀어야 될 수들을 작은 순서대로 넣는다.

2. 그리고 그 우선순위보다 뒤로 풀을 수들을 차례대로 넣는데 후순위 수보다 우선순위로 풀 문제의  수를 카운트한다.

3. 먼저 풀문제들을 먼저 풀고난뒤에 후순위의 문제들을 차례대로 푼다.

4 2, 3 1일때 pq의 순서

3 4 -> 4 -> 1 4 -> 4 -> X -> 2 -> X

count[1] = 0 -> count[2] = 0

 

4 2, 2 1, 3 1일때 pq의 순서

3 4 -> 4 -> X -> 2 -> X -> 1 -> X

count[1] = 1 -> count[2] = 0  -> count[1] = 0

 

 

 

 

핵심

- 오른쪽 수보다 먼저 풀 왼쪽수의 개수를 카운트한다.

- 먼저풀 수를 우선순위 큐에 넣는다.

- 먼저풀 수들(왼쪽수들)을 차례대로 출력하면서 카운트를 줄이고 카운트가 0이되면 그 수를 풀수있도록 우선순위큐에 추가해준다.