백준 2623 음악프로그램 (C++)

2623번: 음악프로그램

위상 정렬을 이용한 문제이ek. 전형적인 위장 정렬 로직을 따라간다. 주의할 점은 보조 PD의 담당 가수를 입력 받을 때 바로 앞 가수에 해당하는 백터 인덱스에 현재 가수를 저장해주어야 하기 때문에 앞 가수를 따로 저장해두어야 하는 점이다. 위상 정렬을 오랜만에 풀어서 그런지 시간이 오래 걸렸다. 위상 정렬에 대해 잘 알아두자.

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

using namespace std;

int N, M;
int inDegree[1001];
vector<int> v[1001];
vector<int> answer;

void solution() {
    queue<int> q;

    for (int i = 1; i <= N; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int cur = q.front();

        q.pop();
        answer.push_back(cur);

        for (int i = 0; i < v[cur].size(); i++) {
            int next = v[cur][i];

            inDegree[next]--;

            if (inDegree[next] == 0) {
                q.push(next);
            }
        }
    }

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

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, b, c;

        cin >> a;
        if (a == 0) continue;
        cin >> b;

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

    solution();

    return 0;
}