[BOJ] 1766번 | 문제집 (C++)

🔗문제 보러가기

1766번: 문제집

 

🧑‍💻풀이 과정

 

위상 정렬(Topological Sort)에 대해 공부한 후, 풀어보려고 골랐던 문제 중 하나입니다. 위상 정렬 알고리즘을 그대로 적용하되, 쉬운 문제부터 풀어야 하니 우선순위 큐(Priority Queue)를 대신 사용해주면 끝인 문제입니다. 이 외에는 더 이상 설명할 내용이 진짜로 없기에, 아래에 코드를 첨부하도록 하겠습니다.

 

✏️소스 코드 및 결과

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

using namespace std;
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

vector<int> GetSolvedOrder(const vector<vector<int>>& graph, vector<int>& inDegrees, int N) {
    priority_queue<int, vector<int>, greater<int>> problems;
    for (int i = 1; i <= N; i++) {
        if (inDegrees[i] == 0)
            problems.push(i);
    }

    vector<int> answers(N + 1);
    for (int i = 1; i <= N; i++) {
        
        int problem = problems.top();
        problems.pop();
        answers[i] = problem;

        for (const auto& other : graph[problem]) {
            if (--inDegrees[other] == 0)
                problems.push(other);
        }
    }

    return answers;
}

int main() {
    FAST_IO
    int N, M;
    cin >> N >> M;

    int from, to;
    vector<vector<int>> graph(N + 1, vector<int>());
    vector<int> inDegrees(N + 1, 0);

    for (int i = 0; i < M; i++) {
        cin >> from >> to;
        graph[from].emplace_back(to);
        inDegrees[to]++;
    }

    vector<int> answers = GetSolvedOrder(graph, inDegrees, N);
    for (int i = 1; i <= N; i++)
        cout << answers[i] << " ";
    
    return 0;
}