[G2] 백준 1766번 문제집 C++ 위상 정렬, 우선순위 큐

리뷰

 

위상 정렬에 우선 순위 큐를 사용하여 최대한 난이도가 낮은 순서로 출력하는 문제

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

 

문제 풀이

1. 문제의 수 n과 선수 문제의 개수 m, 인접 리스트 벡터path를 전역변수로 설정해 준다.
2. n과 m값을 입력 받고, m개의 선수 문제 정보를 인접 리스트 path에 추가해 준다.
3. 선수 문제 개수를 저장할 cnt 벡터를 n + 1크기로, 내부 값을 모두 0으로 초기화 해준다.
4. n개의 문제의 인접 리스트를 순회하며 인접 리스트에 담긴 문제의 개수를 증가시켜 준다.
5. 오름차순 정렬 형태의 우선순위 큐 pq를 초기화 해준다.
6. 다시 n개의 문제를 순회하며 cnt의 개수가 0개라면 pq에 추가해 준다.
7. pq에 요소가 없을 때까지 순회하며 pq의 top요소를 뽑아 cn으로 저장하고 cn을 공백을 구분하여 출력해 준다.
8. 이후 cn의 인접 리스트에 존재하는 문제의 cnt를 1개씩 내려주고 0이 되었다면 pq에 추가해 준다.

 

참고 사항

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.
4. 항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다.

3번 조건에 의해 우선 순위 큐를 사용해 주어야 한다.

 

정답 코드

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

using namespace std;

int n, m;
vector<int> path[32001];

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

	cin >> n >> m;
	while (m--) {
		int a, b; cin >> a >> b;
		path[a].push_back(b);
	}

	vector<int> cnt(n + 1, 0);
	for (int i = 1; i <= n; i++) for (int j : path[i]) cnt[j]++;

	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 1; i <= n; i++) if (!cnt[i]) pq.push(i);

	while (!pq.empty()) {
		int cn = pq.top(); pq.pop();
		cout << cn << " ";
		for (int i : path[cn]) if (--cnt[i] == 0) pq.push(i);
	}
}