[ 백준 2623 ] 음악프로그램 (c/c++)

https://www.acmicpc.net/problem/2623

 

 

[ 문제 요약 ]

보조 PD가 준 순서를 해치지 않는 선에서 전체 가수의 순서를 출력한다. 만약 순서를 정하는 것이 불가능할 경우 0을 출력한다.

 

 

[ 문제 풀이 ]

1. 보조 PD가 준 순서만 유지하면 되기 때문에 단방향을 가지는 그래프로 볼 수 있다.

2. 위상정렬을 통해 문제를 해결할 수 있다.

3. 만약 위상정렬의 결과가 N보다 작을 경우 0을 출력한다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, M, IN[1010];
vector<int> v[1010];
vector<int> ans;
queue<int> q;

int main() {
    cin >> N >> M;
    for (int i=1; i<=M; i++){
        int num, a, b;
        cin >> num >> a;
        for (int j=1; j<num; j++){
            cin >> b;
            v[a].push_back(b);
            IN[b] += 1;
            a = b;
        }
    }
    
    for (int i=1; i<=N; i++) if(!IN[i]) q.push(i);
    while (!q.empty()){
        int cur = q.front(); q.pop();
        ans.push_back(cur);
        for (auto i : v[cur]) if (!--IN[i]) q.push(i);
    }

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

 

 

[ 소스 코드 ]

그래프를 잘 받아서 위상정렬하면 되는 문제였다.