[BOJ알고리즘, C++]#1766_문제집, 위상 정렬, 그래프

 

#1. 문제

1766번: 문제집

 

---

 

#2. 풀이

 

1. 위상 정렬

[자료구조]#6_그래프

 

위상 정렬은 비순환 유향 그래프(DAG)에서 각 정점들의 선행 관계를 유지하며 정점을 나열하는 방법입니다. 일반적으로, 위상 정렬을 구현하는 방법은 두 가지입니다. - DFS, 진입차수 BFS.

 

2. 선행 관계 유지와 더불어, 숫자가 더 작은 것부터 풀어야 한다?

 

1. 진입차수 BFS를 활용하여 각 정점들의 선행 관계를 유지하며 정점들을 나열합니다.
2. 일반적으로, BFS는 큐를 활용하며 각 정점의 선행 관계 유지는 문제없지만, 더 쉬운 문제(여기선 더 작은 숫자의 문제가 더 쉽다고 나와있다)를 먼저 풀어야 하는 대전제가 존재합니다.
3. 더 작은 숫자를 보다 먼저 풀기 위해, 우리는 큐 대신 우선순위 큐를 활용해 볼 수 있습니다!

 

---

 

#3. 코드

 

/*
    [문제] : 선행 관계를 유지하며 그래프의 정점을 나열 한다.
    [설명]
            1. 위상 정렬 알고리즘으로 진입차수 위상정렬을 활용한다.
            2. 일반적으로, 큐를 활용하는 진입차수 위상 정렬에서 더 작은 문제부터 먼저 풀어야되는 조건을 만족시키기 위해 우선순위 큐로 대체
*/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int N, M;
vector<vector<int>> graph;
vector<int> InDegree;

void TopologicalSort(vector<vector<int>> &graph)
{
    // #1. 큐를 선언합니다.
    priority_queue<int, vector<int>, greater<int>> pq;

    // #2. 진입 차수가 0인 정점들을 큐에 삽입합니다.
    for (int i = 1; i <= N; ++i)
    {
        if (InDegree[i] == 0)
            pq.push(i);
    }

    while (!pq.empty())
    {
        int cur = pq.top();
        pq.pop();

        cout << cur << ' ';

        for (const auto &neighbor : graph[cur])
        {
            InDegree[neighbor]--;
            if (InDegree[neighbor] == 0)
            {
                pq.push(neighbor);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    graph.resize(N + 1);
    InDegree.resize(N + 1, 0);

    while (M--)
    {
        int from, to;

        cin >> from >> to;
        graph[from].push_back(to);
        InDegree[to]++;
    }

    TopologicalSort(graph);

    return 0;
}

 

---