[BOJ-1766]문제집

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

[문제요약] 

문제를 아래 규칙과 같이 순서대로 풀어야 한다. 

[규칙]은 아래와 같다.

1. N개 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제라면, "반드시" 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

N개 문제를 풀 때 [규칙2, 3] 을 충족시키며 문제를 먼저 푸는 순서대로 출력해야한다.

[입력]

N M

(1) A1 B1

(2) A2 B2

...

(M) AM BM

N ~ [1, 32,000]  : 문제 수 

M ~ [1, 100,000]:먼저 푸는 것이 좋은 문제에 대한 정보의 개수

다음 줄부터 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 Ai Bi 가 주어진다. 

[규칙2] Ai 는 Bi 보다 먼저푸는 것이 좋다. 

[출력]

[규칙 1,2,3]을 충족시키며 문제를 푸는 순서를 출력한다.

[접근방법]

총 2번 틀리고 AC을 받았다. 

[규칙 3]을 정확하게 이해하지 못해서 2번을 틀렸다. 

위상정렬을 사용해서 문제를 풀이 할 수 있다. WA 2번을 받았을 때는 아래와 같이 생각했다.

1. 문제의 정보가 주어질 때 Ai Bi 에서 Ai를 먼저 풀어야 하므로 Bi 에 Bi → Ai 로 가는 간선을 추가했다.
2. 위 Bi → Ai 를 추가한 이유는 Bi가 낮은 번호인 경우 DFS 를 이용하여 Bi 를 먼저 출력하기 위해서 였다.
3. 만약 Bi 보다 더 먼저 풀어야하는 경우가 있다면 DFS를 사용한다. 
4. 위 경우를 낮은 문제(1~N)부터 시작해서 먼저풀어야 하는 경우를 출력한다. 

이렇게 풀이한 경우는 문제가 있다. 어떤 문제점이냐면 언제나 낮은 번호 문제A가 우선순위가 되는 경우가 발생한다.

먼저 풀 수 있는 문제B가 있는 경우, 즉, 이전에 풀어야 하는 문제가 없는 문제B의 경우이다.

낮은 번호 문제A가 먼저풀어야 하는 문제C가 있는 경우보다 문제 B가 번호가 B < C 인 경우 B를 먼저 풀어야 한다.

하지만 위 방법을 사용하면 C A B 순으로 풀이하게 된다. 그러나 B C A 순으로 풀어야 한다는 것이다. 

그래서 먼저 풀어야 하는 경우가 없는 문제들 중 낮은 번호를 우선적으로 출력해줘야한다. 

그래서 '우선순위 큐' 가 필요하다. 즉, min heap이 필요하다. (낮은 번호부터 우선적으로 출력해야 한다.) 

1) 우선순위 큐에 push 하려면, 먼저 풀어야하는 문제가 없는 경우에 push 할 수 있다.

2) 우선순위 큐에서 pop한 문제는 바로 출력하며, 문제를 이전에 먼저 풀었다면 pop만 한다. 

3) pop 한 문제가 다음으로 풀어야 하는 문제가 더 이상 먼저풀어야하는 문제가 없는 경우, if(deg[there] == 0) 이라면 우선순위 큐에 push 한다.

위 1)-3) 으로 작성하게 되면 AC을 받을 수 있다. 

위상정렬을 사용하지만, 위상정렬과 순서를 고려해줘야하는 문제인 것이다.

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;
 
typedef vector<int> vi;
typedef vector<bool> vb;
const int S = 33333;
int N, M;
vi deg;
vi G[S];
vb vis;
priority_queue<int, vi, greater<int> > PQ;
void init() {
    vis = vb(N + 1, false);
    deg = vi(N + 1, 0);
}
 
 
 
int main() {
    cin >> N >> M;
    
    init();
    for (int i = 0; i < M; i++) {
        int A, B; // A번 문제는 B번보다 먼저풀어 A->B
        cin >> A >> B;
        G[A].push_back(B);
        deg[B]++;
    } 
    for (int i = 1; i <= N; i++) {
        sort(G[i].begin(), G[i].end());
    }
    for (int i = 1; i <= N; i++) {
        if (deg[i] == 0) PQ.push(i);
    }
    while (!PQ.empty()) {
        int here = PQ.top(); PQ.pop();
        if (vis[here]) continue;
        vis[here] = true;
        printf("%d ", here);
        for (auto next : G[here]) {
            if (deg[next] > 0) deg[next]--;
            if (deg[next] == 0) PQ.push(next);
        }
    }
    return 0;
}
// 0% WA
// 9% WA