[백준/c++] 2623번: 음악 프로그램

 

 

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

2623번: 음악프로그램

 

문제 요약

 

가수의 출연 순서를 정하는데, 보조 PD들이 정한 순서가 주어지고 이 순서들을 모아서 전체 가수의 순서를 정해야 한다.

예) 1 4 3 / 6 2 5 4 / 2 3 → 1 6 2 5 4 3 혹은 6 2 1 5 4 3

 

범위

 

가수의 수 N (1 이상 1,000 이하의 정수)

보조 PD의 수 M (1이상 100 이하의 정수)

 

 

 

---

 

 

 

순서를 정해야 하는데, 위상 정렬을 사용하면 된다.

각 정점으로 들어오는 간선의 개수를 카운팅 해서 들어오는 간선이 없는 정점부터 시작해서 그 정점을 제거하고 연결을 풀어준다. 

연결이 풀어지면 들어오는 간선이 없는 새로운 정점이 생길 것이고 반복해서 진행하면 된다.

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 1002
using namespace std;
int n, m, indegree[MAX];
vector<int> graph[MAX];
vector<int> ans;

void input(){
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int cnt, x, y;
        cin >> cnt;
        cin >> x;
        for(int j=2; j<= cnt; j++){
            cin >> y;
            graph[x].push_back(y);
            indegree[y]++;
            x = y;
        }
    }
}

void solution(){
    queue<int> q;
    for(int i=1; i<=n; i++) if(indegree[i] == 0) q.push(i);
    while(!q.empty()){
        int x = q.front();
        ans.push_back(x);
        q.pop();
        for(int i: graph[x]){
            indegree[i]--;
            if(indegree[i]==0) q.push(i);
        }
    }
    if(ans.size() != n) cout << 0; //순서를 정하지 못한 경우
    else for(auto it = ans.begin(); it!=ans.end(); it++) cout << *it << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!