[Beakjoon] 2623 음악프로그램 (C++)

문제 링크

BOJ 2623 : 음악프로그램

문제

음악프로그램에 출연하는 팀의 출연순서를 결정한다.

• N개의 팀이 출연한다.

• M명의 PD가 각자 맡은 팀의 출연 순서를 결정한다.

• PD들이 결정한 출연순서를 유지하며 N개의 팀의 출연순서를 결정한다.

• 여러 경우가 존재하는 경우 그 중 아무거나 출력한다.

• 불가능한 경우 0을 출력한다.

풀이

위상정렬 문제는 딱 봐도 위상정렬이라고 느껴지는 것 같다. (위상정렬 알고리즘 분류를 알고 풀어서 그런가..)

• 유지해야하는 순서를 이용해 그래프를 구성한다.
  추가로 자신에게 연결된 진입간선의 개수를 세어 BF[]배열에 저장한다.

• 특정 노드에 방문하기 위해서는 그 노드 이전에 방문되어야 하는 노드들이 모두 방문이 완료된 상태여야 한다.

• 이 문제의 경우 특정 팀a가 출연할 순서가 되려면 a이전에 출연해야하는 팀들이 모두 출여한 상태여야 한다.

• 따라서 특정 노드에 방문했다면, 해당 노드에 연결된 다음 노드들의 BF[]값을 업데이트 한다. 만약 BF값이 0이 된다면 그 노드는 방문이 가능하므로 다음 방문할 노드들이 저장된 queue 에 저장한다.

코드

#include<bits/stdc++.h>

#define endl "\n"
#define ll long long

using namespace std;

int N,M;
int BF[1010];
vector<int> G[1010];
void Solve() {
    cin>>N>>M;
    int cnt,bf,n;
    for(int i=0; i<M; i++){
        cin>>cnt>>bf;
        for(int j=0; j<cnt-1; j++){
            cin>>n;
            G[bf].push_back(n); BF[n]++;
            bf = n;
        }
    }

    queue<int> Q;
    vector<int> ANS;
    for(int i=1; i<=N; i++){
        if(BF[i]==0) Q.push(i);
    }
    
    while(!Q.empty()){
        n = Q.front(); Q.pop(); ANS.push_back(n);

        for(int i=0; i<G[n].size(); i++){
            if(--BF[G[n][i]]==0) Q.push(G[n][i]);
        }
    }
    
    if(ANS.size()!=N) cout<<0;
    else{
        for(int a: ANS) cout<<a<<endl;
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();

    return 0;
}