[백준] 2623 음악프로그램

백준: 문제

2623번: 음악프로그램

내일 코테를 대비하기 위해 평소에 잘 풀어보지 않은 유형들 위주로 풀고 있다. 이번에는 위상정렬(Topological Sort)!

그래프 노드별로 선후가 정해져있어서 순서를 정하기 위해 크게 2개의 배열을 사용해야 한다.

만약 a → b 식으로 선수, 후수가 정해진다면, 

 

1. 각 노드별 진입차수 inDegree, 즉 b 노드를 방문하기 위해 이전에 방문해야하는 a 노드 개수 기록

2. 각 노드별 후수 노드들, 즉 a에 대한 b 노드들

 

순서는 다음과 같다.

1. 우선 진입차수가 0인 노드를 Queue에 삽입

2. Queue가 empty할 때까지 아래 과정을 반복한다.

2-1. pop한 노드의 후수 노드들의 진입차수를 하나씩 낮춘다.

2-2. 그 중 아직 방문하지 않았고, 진입차수가 0인 노드를 Queue에 삽입한다.

 

이를 통해 풀긴 했는데, 처음에 각 보조 PD별로 위상정렬을 하느라 시간이 엄청나게 걸렸다..어차피 선후 관계는 둘만의 관계이므로 보조 PD의 순서들 중 하나라도 선후 관계가 꼬이면 Queue에 넣지 못하기 때문에 그냥 통합해서 처리해도 문제는 풀린다. 3중 vector 처리할 때 이상한 낌새를 알아차렸어야 했는데ㅠㅠ

 

그래서 각 보조PD의 순서를 통합해서 처리해서 아래와 같이 나름 깔끔한 코드를 얻어냈다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> parents(1001, 0);
vector<vector<int>> children(1001);
int visited[1001];
queue<int> singers;
vector<int> answer;
int main(void){
    int n, m, k;
    int p, c;
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        cin >> k;
        if(k == 0) continue;
        if(k == 1){
            cin >> p;
            continue;
        }
        cin >> p;
        for(int j = 0; j < k - 1;j++){
            cin >> c;
            parents[c]++;
            children[p].push_back(c);
            p = c;
        }
    }
    for(int i = 1;i <= n;i++){
        if(!parents[i]){
            visited[i] = 1;
            singers.push(i);
        }
    }

    while(!singers.empty()){
        int singer = singers.front();
        singers.pop();
        answer.push_back(singer);
        // singer의 child의 indegree--
        for(int j = 0;j < children[singer].size();j++){
            parents[children[singer][j]]--;
        }

        for(int j = 1;j <= n;j++) {
            if(parents[j] == 0 && !visited[j]) {
                visited[j] = 1;
                singers.push(j);
            }
        }
    }

    if(answer.size() != n){
        cout << 0;
    }
    else {
        for(int i = 0;i < n;i++){
            cout << answer[i] << endl;
        }
    }
}