백준 2623 - 음악프로그램, C++, 위상정렬

2623번: 음악프로그램

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

int n, m; // 가수 수, 보조 pd 수
int entrance[1001];
vector<int> singer[1001];

int main(){
    //init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int number_of_singer;
        cin >> number_of_singer;

        vector<int> this_case;

        while(number_of_singer--){
            int singer_number;
            cin >> singer_number;
            this_case.push_back(singer_number);
        }

        for(int j = 0; j < this_case.size(); j++){
            for(int k = j+1; k < this_case.size(); k++){
                // 후순위 가수들을 저장
                singer[this_case[j]].push_back(this_case[k]);
                entrance[this_case[k]]++;
            }
        }
    }

    // Topology Sort
    queue<int> q;

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

    vector<int> singer_order;

    while(!q.empty()){
        int cur_singer = q.front();
        q.pop();
        singer_order.push_back(cur_singer);

        for(int i = 0; i < singer[cur_singer].size(); i++){
            int next_singer = singer[cur_singer][i];
            entrance[next_singer]--;
            if(entrance[next_singer] == 0)
                q.push(next_singer);
        }
    }

    // print
    if(singer_order.size() != n)
        cout << "0\n";
    else{
        for(int i = 0; i < singer_order.size(); i++){
            cout << singer_order[i] << '\n';
        }
    }
    return 0;
}

---

 알고리즘 자체는 단순 위상정렬인데 입력을 어떻게 처리하는가가 문제였습니다.

6 3
3 1 4 3
4 6 2 5 4
2 2 3

 위에처럼 입력이 주어진다고 하면 두번째 줄 3명의 가수가 나오는 부분에서 1 -> 4 -> 3 이라는 형태가 만들어집니다.

일단 각 가수들에게 후순위 가수들이 누구인지 알 수 있게 singer 배열을 선언해 저장을 해 뒀으며 위 1 -> 4 -> 3의 경우에는 진입점이 각각 0, 1, 2가 될 수 있도록 처리해주면 됩니다.

 

 그 후의 과정은 일반적인 위상정렬과 같은 과정입니다.