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

코드

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

using namespace std;
typedef long long ll;

int n,m,cnt, indegree[1003], input[1003];

vector<int> adj[1003];
vector<int> res;

int main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        cin >> cnt;
        for(int j = 0; j < cnt; j++) {
            // python은 split이 있는데 C++은 어떻게 해야할지 몰라서 인풋배열을 하나 만들었다.
            // 인덱스 접근에 주의
            cin >> input[j];
        }
        for(int j = 0; j < cnt - 1; j++) {
            adj[input[j]].push_back(input[j + 1]);
            indegree[input[j + 1]]++;
        }
    }
    queue<int> q;
    for(int i = 1; i < n + 1; i++) {
        if(indegree[i] == 0) {
            q.push(i);
            res.push_back(i);
        }
    }
    while(q.size()) {
        int pn = q.front();
        q.pop();
        for(int i : adj[pn]) {
            indegree[i]--;
            if(indegree[i] == 0) {
                q.push(i);
                res.push_back(i);
            }
        }
    }
    if(res.size() != n) {
        cout << 0 << '\n';
        return 0;
    }
    for(int i : res) cout << i << '\n';
    return 0;
}

풀이

유향 비순환 그래프이고, 조건에 맞는 순서 구하기이기 때문에 위상정렬 알고리즘을 선택했다. 문제에서 주어진 입력 마지막에서 2 3을 3 2로 바꾸면 정할 수 없다고 했는데 이는 사이클이 생기는 경우로 위상정렬을 제대로 할 수 없는 경우이다. 따라서 위상정렬로 순서를 구현하되, 만약 그 순서를 구성한 인원과 주어진 인원이 맞지 않는 경우는 0을 출력했다.