[백준 2623] 음악프로그램

🔗 알고리즘 문제

그래프가 어떻게 구성되어야 할 지 생각해야하는 위상정렬 문제이다. 단순 위상정렬 문제이기에 어렵지 않게 풀 수 있었다.

문제 분석

이 문제는 가수들의 출연 순서가 차례대로 주어질 때, 먼저 나가야 하는 가수부터 순차적으로 출력하면 되는 문제이다.

발상 & 알고리즘 설계

출연 순서가 그래프로 연결되어 있다고 할 때, 출연 순서대로 출력할려면 위상정렬을 하면 된다.

하지만, 이 문제에서는 순서를 정하는 것이 불가능할 경우가 있는데, 이 경우는 그래프에 사이클이 생겨서 위상정렬을 못하는 경우이다.

위상정렬에서 사이클이 생기는지 확인하는 방법은 간단한데, 모든 노드를 탐색하기 전에 큐가 비게 될 경우 위상정렬에 사이클이 생기게 된다.

주어진 출연순서를 그래프로 연결하고 위상정렬을 통해 문제를 해결하였다.

코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    int m;

    vector<int> v[1001] = {};
    vector<int> ans;
    int indegree[1001] = {};

    cin >> n >> m;

    for(int i = 0; i < m; i++) {
        int cnt;
        int last = -1;

        cin >> cnt;

        for (int j = 0; j < cnt; j++) {
            int num;
            cin >> num;

            if (last == -1){
                last = num;
                continue;
            }

            v[last].push_back(num);
            indegree[num]++;
            last = num;
        }
    }

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

    while(!q.empty()){
        int cur = q.front();
        q.pop();

        ans.push_back(cur);

        for(int i = 0; i < v[cur].size(); i++){
            int next = v[cur][i];

            indegree[next]--;
            if(indegree[next] == 0)
                q.push(next);
        }
    }

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