[알고리즘/백준] 1766: 문제집

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

 

 

 

1. 문제 접근

- 총 N개의 문제를 풀어야 한다.

- A → B 라면 A를 풀고 B를 풀어야 함

- 문제 중에서 번호가 작은 문제를 먼저 풀어야 함.

 

즉, 위상 정렬을 하되, 가능한 여러 문제 중에는 가장 번호가 작은 문제를 먼저 선택해야 한다.

 

 

위상 정렬 기반으로 문제를 해결하되, 진입 차수가 0인 노드들 중에서 번호가 작은 것부터 선택하기 위해 우선순위 큐(min-heap) 를 사용해 풀 수 있다!

(일반적인 위상정렬에서는 큐를 사용해 구현함)

 

2. 코드

#include <iostream>
#include <vector>
#include <queue>
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> edges(n + 1);
    std::vector<int> indegree(n + 1);

    int start, end;
    while (m--)
    {
        std::cin >> start >> end;
        edges[start].push_back(end);
        ++indegree[end];
    }

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

    int top;
    while (!q.empty())
    {
        top = q.top();
        q.pop();
        std::cout << top << " ";
        for (const int& nextNode : edges[top])
        {
            if (--indegree[nextNode] == 0)
            {
                q.push(nextNode);
            }
        }
    }
}