BOJ 문제집 (1766) C++

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

---

문제 설명

1~N번까지 총 N개의 문제로 된 문제집이 있습니다. 각 문제의 난이도는 번호와 동일합니다.

어떤 문제를 풀 까 고민하던 중 '먼저 푸는 것이 좋은 문제'가 있다는 것을 깨달았습니다. 그래서 다음 3가지 조건에 따라 문제를 풀 순서를 정하기로 했습니다.

1. N개의 문제를 모두 풀어야 합니다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 반드시 먼저 푸는 것이 좋은 문제를 다 푼 후 풀어야합니다.
3. 가능하면 쉬운 문제부터 풀어야 합니다.

문제의 개수와 먼저 푸는 것이 좋은 문제에 정보가 주어질 때, 주어진 조건을 만족하며 문제 풀이 순서를 결정해주는 프로그램을 작성하시오. (항상 문제를 모두 풀 수 있는 경우만 입력으로 주어집니다.)

---

아이디어

1. '먼저 푸는 것이 좋은 문제'가 있다는 것은 문제간의 선후관계가 있다는 뜻이니 위상정렬입니다.

2. 가능하면 쉬운 문제부터 풀어야 한다는 얘기는, 문제마다 우선순위가 다르기 때문에 우선순위 큐를 사용하면 좋을 것 같습니다.

3. 문제 개수가 4, 간선이 2개인 경우 간선이 각각 1 → 4, 3 →2 인 경우 올바른 정답은 1 3 2 4입니다.🔗

위상정렬이 여러개이기 때문에 여러 위상정렬 중 가장 낮은 난이도의 문제를 푼 후, 다음 문제는 다른 위상 정렬에 존재할 수 있습니다.

---

코드

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<priority_queue<int, vector<int>, greater<int>>> graph(32001);
vector<int> input(32001);
vector<bool> visited(32001);

int main()
{
    cin >> n >> m;
    
    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push(b);
        input[b] += 1;
    }

    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i = 1; i <= n; i++)
    {
        if(input[i] == 0)
        {
            pq.push(i);
        }
    }

    while(!pq.empty())
    {
        auto cur = pq.top(); pq.pop();
        visited[cur] = true;
        cout << cur << ' ';

        while(!graph[cur].empty())
        {
            auto next = graph[cur].top(); graph[cur].pop();
            input[next] -= 1;
            if(visited[next])
                continue;
            if(input[next] != 0)
                continue;
            pq.push(next);
        }
    }
}

메모리 4084KB, 시간 80ms