[C/C++] 백준 #1766 문제집(위상정렬)

이번 문제는 일을 처리하는데 있어서 우선순위가 주어진 경우 그것을 해결하는 방법입니다.

 

1. N개의 문제는 반드시 풀어야 한다.

2. 먼저 푸는 것이 좋은 문제가 있는 경우에는 더 쉬운 문제를 먼저 풀어야 한다.

3. 쉬운 문제가 있다면, 쉬운 문제를 먼저 풀어야 한다.

 

1번 조건과 2번 조건만을 보면 위상 정렬입니다.

3번 조건은 위상정렬을 할 때, 인입간선이 없는 것들중에 문제 번호가 적은 것을 우선 선택할 수 있도록, 문제 번호대로 우선순위 큐를 작성하면 됩니다.

 

그래서 위상정렬을 근간으로 우선순위 큐를 사용하면 됩니다.

저는 조금 다르게 작성하기는 했지만, 기본적인 취지는 비슷합니다.  아마 지금 작성했다면, 위에 설명한대로 작성했을 것 같네요.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//-------------------------------------------------------------
//    baekjoon #1766
//        - by Aubrey Choi
//        - created at 2019-11-22
//-------------------------------------------------------------
#include <stdio.h>
#include <queue>
#include <vector>

int main()
{
    int n, m, a, b; static int v[32000];
    std::vector<int> adj[32000];
    std::priority_queue<int, std::vector<int>, std::greater<int> > q;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&a,&b); a--,b--;
        v[b]++; adj[a].push_back(b);
    }
    for(int i=0;i<n;i++) q.push((v[i]<<16)|i);
    while(!q.empty())
    {
        a = q.top(); q.pop(); b=a&0xffff; a>>=16;
        if(v[b]!=0) continue;
        v[b]=-1; printf("%d ", b+1);
        for(auto k:adj[b])
        {
            v[k]--;
            q.push((v[k]<<16)|k);
        }
    }
    putchar('\n');
}

 

workbook