백준/1766번/문제집/골드2

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

문제 설명

Site: Baekjoon
Number: 1766
Category: Topology Sort
Rank: Gold 2

3가지 조건에 따라 주어지는 문제들을 해결할 때, 문제를 해결하는 순서를 출력하는 문제입니다.

전형적인 위상 정렬 문제로 위상 정렬 해결 방법을 적용하면 쉽게 해결할 수 있습니다.

문제 풀이

위상 정렬에서 필요한 각 문제 별 degree를 저장하기 위해 degree 배열을 생성합니다.

다음과 같은 과정을 따라 문제를 해결합니다.

1. 주어진 연결 내용을 vector에 삽입하며 도착 지점의 degree를 올립니다.

2. 주어진 문제 중 가장 작은 난이도 부터 해결하므로 priority_queue를 사용하여 degree가 0인 문제를 모두 pq에 넣습니다.

3. pq가 빌 때 까지 pq의 원소를 빼며 출력하고 pq의 원소와 연결된 모든 문제의 degree를 줄입니다.

4. 줄인 후 degree가 0이라면 해당 문제도 pq에 넣습니다.

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

using namespace std;

int degree[32001];

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

    int N, M;
    cin >> N >> M;

    vector<vector<int>> edges(N+1, vector<int>());

    for(int i = 0; i < M; i++)
    {
        int start, dest;
        cin >> start >> dest;

        edges[start].push_back(dest);
        degree[dest]++;
    }

    priority_queue<int, vector<int>, greater<>> pq;

    for(int i = 1; i < N+1; i++)
    {
        if (degree[i] == 0)
            pq.push(i);
    }

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

        cout << cur << ' ';

        for(int i = 0; i < edges[cur].size(); i++)
        {
            if (--degree[edges[cur][i]] == 0)
                pq.push(edges[cur][i]);
        }
    }

    return 0;
}