[백준] 1766번 문제집 [C++]

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

1766번: 문제집

---

---

접근 방식

위상정렬과 우선순위 큐를 이용하여 문제를 풀었다.

 

우선순위 큐를 쓰는 이유는 3번조건인 난이도가 쉬운 문제부터 풀어야 하기 때문에, 푸는게 가능한 문제중에서 가장 숫자가 작은 숫자부터 풀기 위해서이다.

 

먼저, X번의 문제를 풀기위해서 선행적으로 풀어야 하는 문제들이 i개 있다고 생각하자.

그렇다면 이 i의 값이 0이 되는 문제는 선행으로 아무것도 풀지 않아도 되기 때문에 먼저 우선순위 큐에 넣어준다.

그 후에, i의 값이 0이 되는 문제를 a번 이라고 한다면, a번을 풀어야 풀 수 있는 문제들이 있을 것이다.

그 문제들은 이제 a번이 풀렸기 때문에 선행적으로 풀어야 하는 문제들이 i-1개가 되는 것이다.

따라서 이 과정에서 i값 1개를 줄여주는데, 이 때 i가 0이 된다면 그 문제도 풀 수 있는 문제기 때문에, 우선순위 큐에 넣어준다.

이러한 과정을 우선순위큐가 empty상태가 될 때 까지 반복해주면, 우리가 원하는 답을 구할 수 있다.

---

코드

#include <iostream>
#include<queue>
#include<vector>
using namespace std;
priority_queue<int, vector<int>, greater<int>> pq; //쉬운 문제부터 저장하기 위해서
priority_queue<int, vector<int>, greater<int>> d[32001]; //쉬운 문제부터 저장하기 위해서
int c[32001];//문제를 풀기위해 풀어야하는 선행 문제들의 갯수를 저장하는 변수
int n, m;
bool flag[32001]; //이미 푼 문제인지 확인
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		d[x].push(y);
		c[y]++;
	}
	for (int i = 1; i <= n; i++) {
		if (c[i] == 0) {
			flag[i] = true;
			pq.push(i);

		}
	} //선행적으로 풀어야 하는 문제가 없는 문제들을 우선순위 큐에 집어넣음
	while (!pq.empty()) {
		int x = pq.top();
		cout << x << ' ';
		pq.pop();
		int k = d[x].size();
		for (int i = 0; i < k; i++) {
			if (!flag[d[x].top()]) { //푼 문제들은 패스
				c[d[x].top()]--; //선행적으로 풀 문제의 갯수를 줄여줌
				if (c[d[x].top()] == 0) { //만약에 선행적으로 풀어야 할 문제가 더 없다면
					pq.push(d[x].top()); //큐에 넣어줌
					flag[d[x].top()] = true;
				}
			}
			d[x].pop();
		}
	}
}

---

단순한 그래프 문제라고 생각했는데, 위상 정렬이라는 새로운 요소가 있어서 공부를 하고 풀게 되었다.

심지어 어제 푼 문제(ACM Craft)도 위상정렬 카테고리에 있던데 그냥 dp로 해결된게 의문,,

위와같이 선행적으로 무언가를 해야 하는 문제가 있다면 위상정렬을 사용해서 하면 쉽게 풀 수 있을것 같다.