1766 문제집

---

문제 정의

• 문제의 개수 N이 주어진다.
• N 개의 문제를 모두 풀어야만 한다.
• 먼저 푸는 것이 좋은 문제가 있는 경우, 먼저 푸는 것이 좋은 문제를 반드시 먼저 푼다.
• 가능하면 쉬운 문제부터 풀어야 한다.
• 문제집의 번호는 난이도와 비례한다.

입력

• 첫째줄에 문제의 수 N(1<=N<=32000)과 문제의 정보M(1<=M<=100000)이 주어진다.
• 둘째줄부터 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주어진다.
• 이 때 A문제는 B를 풀기전 풀어보면 좋은 문제이다.

출력

• 문제를 풀어야 하는 순서대로 빈칸을 사이에 두고 출력한다.

---

Solution

서로 얽힌 관계에 있고 할 일의 우선순위를 두는 문제이므로 위상정렬을 사용한다.
거기에 추가적으로 Count sort를 사용하였다.

자료의 저장은우선순위 큐와 vector를 활용하였다.
문제를 풀어야하는 정보는 vector를 이용하여 A와 B 순서쌍을 links라는 2차원 배열에 담아주었다.

각 문제를 풀기전 풀어야하는 수를 count배열에 담아준다.
예제를 봐보자.

4 2
4 2
3 1

4개의 문제 1, 2, 3, 4번이 주어질 때
2번 문제를 풀기전에 4번을 풀어야하고,
1번 문제를 풀기전에 3번을 풀어야한다.
그럼 count 배열은 다음과 같아진다.
count[] = [ 1, 1, 0, 0]
0번째 배열은 문제 1을 풀기전 풀어야하는 문제의 수이다.
1번째 배열은 문제 2을 풀기전 풀어야하는 문제의 수이다.
그럼 먼저 풀 수 있는 문제는 규칙에 따라 3과 4중 더 쉬운 문제인 3일 것이다.
다음으로 3번을 풀었으니 배열은 다음과 같이 변화한다.
count[] = [ 0, 1, 0, 0]
그럼 1번과 4번의 선택이 가능해졌으므로 더 쉬운 1번 문제를 푼다.
다음으로 선택 가능한 문제는 4번이므로 4번을 푼다. 마지막으로 남은 2번을 푼다.
그러면 문제 풀이 순서는 다음과 같다.
3 -> 1 -> 4 -> 2
이걸 우선순위큐를 이용하면 count[i] 가 0인 것들을 모두 우선순위 큐에 넣어주고 하나를 pop()하여 문제를 해결할 때마다 업데이트 해주면 문제가 해결된다.

---

정답 코드

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

using namespace std;

vector<int>links[32001]; // i번째 문제를 풀면 그 다음문제들에 접근하기 위한 배열
int counts[32001]; // i번째 문제를 풀기 전 풀어야 하는 문제의 개수 

void sol(int n) {
	priority_queue<int, vector<int>, greater<int>>pro;
    // 문제를 하나씩 pop()해줄 priority_queue
	for (int i = 1; i <= n; i++) {
		if (counts[i] == 0) {
			pro.push(i); 
            // 최초의 priority_queue를 만들기 위해 풀 수 있는 모든 문제 저장 
		}
	}
	while (!pro.empty()) { // 모든 문제를 풀기 전까지 반복
		int cup = pro.top(); // 가장 쉽고 풀 수 있는 문제부터 체크
		pro.pop();
		cout << cup << ' ';
		for (auto i : links[cup]) {
			if (--counts[i] == 0)
				pro.push(i);
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		counts[b]++;
		links[a].push_back(b);
	}
	sol(n);
	return 0;
}