BOJ - 2623 음악프로그램

2623번 음악프로그램

PD들이 음악 프로그램에 출연할 자기 담당 가수들의 순서를 정해 두었다.

모든 PD들의 요구조건을 만족시키도록 가수들의 순서를 정하는 것이 문제이다.

문제 해결 전략

가수들의 순서가 다 정해져 있고, 모든 가수들을 출연시켜야 하기 때문에 위상정렬을 통해 문제를 해결할 수 있다.

순서가 한번에 주어지기 때문에 그래프를 생성할 때 주의하여 생성하여야 한다.

예를들어 1 2 3 4 로 순서가 주어진다면 1번에 2,3,4를 연결하는 것이 아니라 1->2->3->4 가 되도록 연결해 준다.

그래프를 생성하면서 부모노드의 수 역시 저장해 준다.

그리고 위상정렬을 실행하며 부모노드가 없는 경우 ans벡터에 삽입해 준다.

문제의 조건으로 만족하는 조건이 없는 경우 0을 출력하라고 되어 있는데, 만족하지 못하는 경우는 순서가 모순이 되는 경우이다.

예를들어 2->1->3과 2->3->1이 주어진다면 1과 3은 절대 부모노드가 없는 경우가 생기지 않으므로 ans벡터에 삽입된 원소의 수가 가수의 수보다 적을 것이다.

이를 활용하여 예외 처리를 해 주면 된다.

코드

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

int n,m;
vector<int> v[1001];
vector<int> ans;
queue<int> q;
int ind[1001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for(int i=0;i<m;i++){
        int a;
        cin >> a;
        int b;
        cin >> b;
        for(int j=1;j<a;j++){
            int c;
            cin >> c;
            v[b].push_back(c);
            ind[c]++;
            b=c;
        }
    }

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

    while(!q.empty()){
        int x = q.front();
        q.pop();
        ans.push_back(x);
        for(int i=0;i<v[x].size();i++){
            ind[v[x][i]]--;
            if(ind[v[x][i]] == 0)
                q.push(v[x][i]);
        }
    }

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

    return 0;
}

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