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

문제 이해

- 음악 프로그램 PD인 남일이가 보조 PD에게 순서를 정해오게 한다.

- 각 순서들을 모아서 전체 가수의 순서를 정해야 한다.

- 만약 불가능 하다면 0을 출력한다.

- 답이 여러 개인 경우 아무거나 하나를 출력한다.

 

- N: 가수의 수 (1 ~ 1,000, 10^3)

- M: 보조 PD의 수 (1 ~ 100, 10^2)

 

 

문제 풀이

순서가 정해진 몇 쌍으로부터 전체 순서를 구하는 문제 --> 위상 정렬!

 

이 문제의 특징적인 점은 주어지는 순서들이 전체 순서를 정하는 것이 불가능한 경우도 있다는 것이다.

즉, 순환 그래프가 만들어질 수 있다는 점이다.

 

 

그렇다면 순환 그래프는 어떻게 확인할 수 있을까?

답은 바로, 위상정렬이 끝났을 때 정점으로 들어오는 간선이 남아있는 경우이다.

 

while문이 끝난 뒤 정점으로 들어오는 간선의 개수를 체크하여 불가능한 경우를 확인해볼 수 있다!

for(int i = 1; i <= n; i++){
        if(inDegree[i] > 0){
            cout<<"0";
            return 0;
        }
    }

 

 

전체 코드

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

int n, m;
vector<int> v[32005];
int inDegree[32005];
queue<int> q;

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

    cin>>n>>m;
    for(int i = 0; i < m; i++){
        int cnt, tmp;
        cin>>cnt;

        int a = 0, b = 0;
        while(cnt--){
            a = b;
            cin>>tmp;
            b = tmp;
            
            if(a == 0) continue;

            v[a].push_back(b);
            inDegree[b]++;
        }
    }
    for(int i = 1; i <= n; i++){
        if(inDegree[i] == 0){
            q.push(i);
        }
    }

    vector<int> ans;

    while(!q.empty()){
        int now = q.front();
        q.pop();
        ans.push_back(now);

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

            if(inDegree[next] == 0){
                q.push(next);
            }
        }
    }

    for(int i = 1; i <= n; i++){
        if(inDegree[i] > 0){
            cout<<"0";
            return 0;
        }
    }

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

 

위상 정렬의 기능 중 하나인 순환 그래프인지 체크하는 것을 확인해볼 수 있던 문제였다!