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

백준

---

🤔문제 이해

먼저 푸는 게 좋은 문제는 먼저 풀어주되 번호가 낮은 문제를 더 우선적으로 풀면 된다. 출력으로는 문제 푸는 순서를 출력하면 되는 문제이다.

---

💡첫번째 아이디어

먼저 푸는 것이 좋은 문제가 있는 문제를 모두 순서대로 출력해주고, 나머지 문제들을 오름차순으로 출력해주면 된다고 생각했다. 

 

❌첫번째 제출

제대로 풀었다고 생각했고, 출력 값도 잘 나왔다.문제를 다시 읽어보고 반례를 생각해보니 문제의 조건에 "가능하면 쉬운 문제부터"라는 조건을 빠뜨렸었다..!

---

💡두번째 아이디어

먼저 푸는 것이 좋은 문제가 없는 문제의 in_degree도 0으로 초기화해서 가능하면 쉬운 문제들부터 출력되게 해주었다 .

 

🔥풀이🔥

위상정렬 알고리즘을 이용하였다.

우선순위큐를 사용하여 in_degree가 0인 문제 먼저 출력해주고,

먼저 푸는 것이 좋은 문제의 경우 그 다음 문제의 in_degree의 값을 -1해줬을 때 그 값이 0이라면 큐에 push해준다.

큐가 빌 때까지 반복해주면 끝!

 

 

❌트러블 슈팅

문제를 제대로 읽고, 여러 상황에 조건을 적용해보며 이해해 봐야겠다.

---

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

using namespace std;

int n, m;
int in_degree[33000];
vector<vector<int>> v;
priority_queue<int> q;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    v.resize(n + 2);
    int a, b;

    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        in_degree[b]++;
    }

    for (int i = 1; i <= n; i++) {
        if (in_degree[i] == 0) {
            q.push(-i);
        }
    }

    while (!q.empty()) {
        int num = -q.top();
        q.pop();
        cout << num << " ";

        for (int next: v[num]) {
            if (--in_degree[next] == 0) {
                q.push(-next);
            }
        }
    }
}