BOJ 2623 : 음악 프로그램

풀이요약

위상정렬

풀이상세

1. 주어진 순서들을 가지고, 하나의 그래프를 형성한다. 그래프 형성과정에서 해당 노드에 진입할 수 있는 차수들도 함께 저장한다.

2. 만약 그래프를 탐색하며 현재 차수가 0이 되는 노드들을 먼저 탐색한다. 만약, 전체 노드를 탐지하기 전에 0인 노드가 존재하지 않는 경우는 주어진 그래프로는 전체 순서를 정할 수 없는 상황인 것이다. 다음 노드로 이동 시에는 다음 노드에 대한 진입 차수를 1개 씩 빼준다. 만약 0이 된다면 이 노드 역시 다음 탐색 순서로 지정한다.

3. 이 과정을 반복하여 $N$ 까지 도달하는 경우, 전체 탐색 순서를 반환한다.

#include <iostream>
#include <vector>
#include <queue>

#define MAX 1004
using namespace std;
int N, M;
vector<int> v[MAX];
int d[MAX], res[MAX];

void input() {
    cin >> N >> M;
    int cnt, prev, next;
    for (int i = 0; i < M; i++) {
        cin >> cnt >> prev;
        for (int j = 1; j < cnt; j++) {
            cin >> next;
            v[prev].push_back(next);
            d[next]++;
            prev = next;
        }
    }
}

void solve() {
    queue<int> q;
    for (int i = 1; i <= N; i++) {
        if (d[i] == 0) q.push(i);
    }

    for (int i = 1; i <= N; i++) {
        if (q.empty()) {
            cout << 0;
            return;
        }
        int curr = q.front();
        q.pop();

        res[i] = curr;
        for(auto next : v[curr]) {
            if(--d[next] == 0) q.push(next);
        }
    }

    for(int i=1; i<=N; i++) {
        cout << res[i] << "\n";
    }
}

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