[C++][백준 2623] 음악프로그램

[문제]

2623번: 음악프로그램 (acmicpc.net)

2623번: 음악프로그램

[문제 풀이]

위상정렬을 살짝 응용한 문제이다.

각 PD들은 제일 처음에 N명을 받을것을 입력하고 그 뒤에 가수들을 n 명 입력받고 각 가수들은 해당 순서대로 나오게 되어 있다. 즉, 앞에 있는 가수가 먼저 나와야 뒤에 있는 가수가 나온다.

3 1 4 3 같은 경우에 처음에 입력받은 값은 3이니 뒤에 3명의 가수가 나오고 1번 가수가 나오면 그 뒤에 4번 가수, 그 뒤에 3번 가수가 나오게 되어 있다.

만약 0을 입력받거나 1을 입력 받는다면 굳이 그 뒤에 의존 관계가 생기지 않으니 패스를 하면 된다.

[회고]

3 1 4 3 같은 경우에 1 -> 4 고  그 다음에는 4 -> 3 으로 접근이 되어야 하는데 이를 모두 1 -> 4, 1 -> 3으로 하고 있었던 것을 눈치채지 못했다. 덕분에 계속 틀리는데 뭐가 잘못되었는지 눈치를 못채었고 틀렸습니다를 무수하게 받음...

디버깅을 앞으로 잘 하는 습관을 들자.

[코드]

#include <iostream>
#include <vector>
#include <queue>
#define endl "\n"

using namespace std;

vector<int> graph[1010];
vector<int> result;
int adj[1010];
int n,m;

void topological(){

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

    while(q.size() > 0){
        int cur = q.front();
        q.pop();
        result.push_back(cur);

        for(int i = 0;i<graph[cur].size();i++){
            int next = graph[cur][i];
            adj[next] -= 1;
            if(adj[next] == 0){
                q.push(next);
            }
        }
    }

    return;
}

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

    while(m--){
        int num;
        cin>>num;
        if(num == 0){
            continue;
        }
        else if(num == 1){
            int b;
            cin>>b;
            continue;
        }

        int singer;
        cin>>singer;
        int subSinger;

        for(int i = 1;i<num;i++){
            cin>>subSinger;
            graph[singer].push_back(subSinger);
            adj[subSinger] += 1;
            singer = subSinger;
        }
    }

    topological();

    if(result.size() != n){
        cout<<0<<endl;
    }
    else{
        for(int i = 0;i<result.size();i++){
            cout<<result[i]<<endl;
        }
    }


    return 0;
}