백준 1766번. 문제집(c++) / 위상정렬

위상정렬을 이론으로는 알고 있었지만 직접적으로 활용해서 푸는 문제는 처음 접했다.

요즘 라인, 네이버 등 it회사에서 자주 출제되는 경향이 있어서 연습삼아 풀어보았다.

 

위상정렬에 대한 이론 정리는 아래 블로그에서 아주 잘 정리해놓아서 참고하시면 될 것이다.

gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

[알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog

 

이 문제는 우선순위큐를 사용해서 위상정렬을 그대로 구현한 문제이기 때문에 코드를 참고하시는게 좋을 것 같습니다.

 

// 문제집
#include <queue>
#include <vector>
#include <iostream>
 
using namespace std;
 
int n, m, a, b;
int isDone[32001] = {0, };
vector<int> seq[32001];
priority_queue<int, vector<int>, greater<int>> pq;
 
int main()
{
    cin>>n>>m;
    for(int i=0; i<m; i++){
        cin>>a>>b;
        isDone[b]++;
        seq[a].push_back(b);
    }
 
    for(int i=1; i<=n; i++){
        if(isDone[i]==0){
            pq.push(i);
        }
    }
 
    while(!pq.empty()){
        int problem = pq.top();
        pq.pop();
 
        cout<<problem<<" ";
 
        for(int i=0; i<seq[problem].size(); i++){
            int next = seq[problem][i];
            isDone[next]--;
            if(isDone[next]==0){
                pq.push(next);
            }
        }
    }
 
    cout<<"\n";
    return 0;
}