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

2623번: 음악프로그램

위상 정렬

---

1. 문제 해결 아이디어

예제 입력을 그래프로 나타낸 것이다.

 

indegree를 활용한 위상 정렬로 풀었다.

 

입력을 받을 때 각 정점마다 indegree가 몇 개 인지 배열에 저장해준다.

 

위상 정렬 bfs를 수행하면서 현재 정점의 자식 정점들의 indegree를 하나씩 빼준다.

만약 자식 정점의 indegree가 0이 된다면 현재 정점을 queue에 넣어준다.

queue에 넣는다는 의미는 자신보다 먼저 수행되어야 할 정점이 없어서 현재 정점을 바로 실행해도 무방하다는 의미라고 볼 수 있다.

 

---

2. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
 
int N, M;
int indegree[1001];
vector<int> Singer[1001];
 
void input(){
    cin >> N >> M;
    for(int k = 0; k < M; k++){
        int nos, sn, firstsn;
        cin >> nos >> firstsn;
        for(int i = 1; i < nos; i++){
            cin >> sn;
            Singer[firstsn].push_back(sn);
            indegree[sn]++;
            firstsn = sn;
        }
    }
}
 
void topological(){
    vector<int> result;
    
    queue<int> que;
    bool visited[1001];
    memset(visited,0, sizeof(visited));
    
    for(int i = 1; i <= N; i++){
        if(indegree[i] == 0){
            que.push(i);
            visited[i] = true;
        }
    }
    
    while(!que.empty()){
        int now = que.front();
        que.pop();
        
        result.push_back(now);
        
        for(int &next : Singer[now]){
            if(visited[next]) continue;
            
            if(--indegree[next] == 0){
                visited[next] = true;
                que.push(next);
            }
        }
    }
    
    for(int i = 1; i <= N; i++){
        if(indegree[i]){
            cout << 0;
            return;
        }
    }
    for(int &w : result){
        cout << w << "\n";
    }
}
 
int main(){
    input();
    topological();
    
    return 0;
}