[BOJ] 2623번 | 음악프로그램 (C++)

🔗문제 보러가기

2623번: 음악프로그램

 

🧑‍💻풀이 과정

 

위상 정렬을 사용해 풀 수 있는 문제인데, 사이클(Cycle) 감지 조건을 하나 더 넣어야 하는 문제입니다. 순서를 정하는 게 불가능한 경우는 각 가수들의 순서에 사이클이 있는 경우가 됩니다. 이는 모든 노드를 돌기 전에 큐(Queue)가 비었을 경우로 탐지 할 수 있습니다.

 

✏️소스 코드 및 결과

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

using namespace std;
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

vector<int> Solution(const vector<vector<int>>& graph, vector<int>& inDegrees, int N) {
    vector<int> answers(N + 1);
    queue<int> nextSingers;

    for (int i = 1; i <= N; i++)
        if (inDegrees[i] == 0)
            nextSingers.push(i);
    
    for (int i = 1; i <= N; i++) {
        if (nextSingers.empty())
            return {0, 0};
        
        int singer = nextSingers.front();
        answers[i] = singer;
        nextSingers.pop();

        for (const auto& other : graph[singer]) {
            if (--inDegrees[other] == 0)
                nextSingers.push(other);
        }
    }

    return answers;
}

int main() {
    FAST_IO
    int N, M, singerCount;
    cin >> N >> M;

    vector<vector<int>> graph(N + 1, vector<int>());
    vector<int> inDegrees(N + 1, 0);

    for (int i = 0; i < M; i++) {
        cin >> singerCount;
        int from, to;

        for (int i = 0; i < singerCount; i++) {
            cin >> to;

            if (i == 0) {
                from = to;
                continue;
            }

            graph[from].emplace_back(to);
            inDegrees[to]++;
            from = to;
        }
    }

    vector<int> answers = Solution(graph, inDegrees, N);
    for (int i = 1; i < answers.size(); i++)
        cout << answers[i] << "\n";

    return 0;
}