[백준(BOJ)] 2623번 : 음악 프로그램 C++ 풀이(위상정렬)

접근:

노드간 순서를 정렬하는 것이기 때문에, 위상정렬로 해결하면 된다.

 

전략:

각 순서에 대해서 그래프를 그려주고, 그래프 중에서 진입차수가 0인 노드부터 처리하면서, 그 노드로 부터 진입하는 노드의 진입차수를 하나 씩 줄여간다. 그리고 줄인 차수 중 0인 노드를 다시 탐색하면서 반복한다.

만약 처리하지 못한 노드가 있는데, 진입차수가 0인 것이 없다면 순서를 처리 할 수 없는 상태이고,

처리 수랑 전체 노드 수가 같다면, 그 처리 순서대로 출력하면 된다. 

 

코드:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,m;
vector<int> edge[1002];
int num[1002];

int main(){
    cin >> n >> m;

    for(int i=0;i<m;i++){
        int t;
        cin >> t;
        int st=0,en=0;

        cin >> st;
        for(int j =1; j<t;j++){
            cin >> en;
            edge[st].push_back(en);
            num[en]++;
            st = en;
        }
    }


    queue<int> q;

    for(int i =1;i<=n;i++){
        if(num[i] == 0){
            q.push(i);
        }
    }
    vector<int> v;

    while(!q.empty()){
        auto cur = q.front();q.pop();
        v.push_back(cur);

        for(auto next : edge[cur]){
            if(--num[next]==0){
                q.push(next);
            }
        }
              
    }

    if(v.size() != n)
    {
        cout << 0 << '\n';

    }else{
        for(auto e : v){
            cout << e << '\n';
        }
    }
    return 0;
}