[1766번] 문제집

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 위상 정렬 :: http://www.crocus.co.kr/716

2. 우선순위 큐 

위상 정렬을 이용하여 푸는 문제이다.

보통 문제의 경우에는 일반큐를 이용하여 그 큐에 들어가는 순서대로 꺼내어 위상 정렬에 이용하였지만,

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제라면, 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

위의 3번 조건에 의해 이번 문제는 문제집 번호가 큐에 있을수록 먼저 꺼내어 확인하여야 한다는 것이 다른 점이다.

따라서 이문제는 우선순위 큐를 이용하여 해결한다면 O(nlgn)에 해결 할 수 있다.

이 문제를 충분히 접하고 위의 내용을 본다면 우선순위 큐를 왜 써야 하는지 이해가 되리라 믿는다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
#include <functional>
 
using namespace std;
 
vector<int> vc[32001];
int line[32001];
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++)
    {
        int cur, prev;
 
        // prev값을 먼저 받아
        scanf("%d %d", &prev, &cur);
 
        line[cur]++;
        vc[prev].push_back(cur);
    }
 
    int result[32001];
    priority_queue<int, vector<int>, greater<int>> q;
 
    for (int i = 1; i <= n; i++)
        if (line[i] == 0)
            q.push(i);
 
    for (int i = 0; i < n; i++)
    {
        int cur = q.top();
        q.pop();
 
        result[i] = cur;
 
        for(int j = 0 ; j < vc[cur].size(); j++)
        {
            int next = vc[cur][j];
 
            if (--line[next] == 0)
                q.push(next);
        }
        
    }
    
    for (int i = 0; i < n; i++)
        printf("%d ", result[i]);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>