(C++) 백준 2623 음악프로그램

문제 및 풀이

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

위상정렬 문제~

• v[x] : x가 나온 다음 출현할 수 있는 가수들
• edge[x] : x가 출현하기 전 나오는 가수들의 개수 (들어오는 방향의 간선)

1. edge[x]==0 이면 이전 조건 없이 출현 가능하므로 큐에 입력한다.
2. x에 연결된 노드들 (v[x])를 돌며 간선 값을 1씩 감소시킨다.
3. edge가 0이 된 경우 이전 조건이 모두 충족된 것이므로, 다시 큐에 입력시켜 다음 노드들을 탐색한다.

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

int N,M,x;
vector<int> v[1005];
int edge[1005];
vector<int> ans;


void topology(){

    queue<int> q;

    for(int i=1; i<=N; i++) {
        if(edge[i]==0) {
            ans.push_back(i);
            q.push(i);
        }
    }

    while(!q.empty()){

        int tmp = q.front();
        q.pop();

        for(int i=0; i<(int) v[tmp].size(); i++){
            int next = v[tmp][i];
            if(--edge[next]==0) {
                ans.push_back(next);
                q.push(next);
            }
        }

    }

    return;
}



int main(){

    cin>>N>>M;

    for(int i=0; i<M; i++){
        cin>>x;
        vector<int> tmp(x);
        for(int i=0; i<x; i++) cin>>tmp[i];
        for(int i=0; i<x-1; i++) {
            v[tmp[i]].push_back(tmp[i+1]);
            edge[tmp[i+1]]++;
        }
    }

    topology();

    if(ans.size()==N) for(int i=0; i<N; i++) cout<<ans[i]<<'\n';
    else cout<<"0";

}