[C++] 백준/Gold/2623. 음악프로그램

문제: 음악 프로그램 (백준 2623번)

문제 분석

이 문제는 사이클 탐색과 위상 정렬을 결합한 문제이다.
지문은 길지만, 문제의 핵심은 주어진 조건에 따라 유방향 그래프를 만들고, 그 그래프에서 사이클이 있는지 확인한 뒤, 사이클이 없다면 위상 정렬을 수행하는 것이다.

해결 접근

1. 사이클 탐색
   • 각 가수 간의 선후 관계를 유방향 그래프로 표현한다.
   • 사이클이 있으면 그 그래프는 위상 정렬이 불가능하다.
   • DFS를 사용하여 그래프에서 사이클을 탐지한다.
2. 위상 정렬
   • 사이클이 없으면 위상 정렬을 통해 가수들의 순서를 결정한다.
   • 위상 정렬은 진입 차수가 0인 노드를 먼저 처리하며, 이를 통해 순서를 구한다.
3. 우선순위 큐
   • 위상 정렬을 수행하는 중에 여러 노드가 진입 차수가 0일 때, 우선순위 큐를 사용하여 가장 작은 번호부터 처리하도록 한다.

알고리즘 설명

1. 입력 처리 및 그래프 구축
   • 주어진 가수 간의 선후 관계를 바탕으로 유방향 그래프를 만든다.
   • 각 노드(가수)에 대해 진입 차수를 계산한다.
2. DFS로 사이클 탐지
   • DFS를 통해 사이클이 존재하는지 확인한다.
   • DFS 도중에 아직 끝나지 않은 노드를 다시 방문하면 사이클이 발생한 것이다.
3. 위상 정렬
   • 진입 차수가 0인 노드를 우선순위 큐에 넣고, 큐에서 하나씩 꺼내며 해당 노드의 후속 노드들의 진입 차수를 감소시킨다.
   • 모든 노드를 처리하면 위상 정렬이 완료된다.
4. 결과 출력
   • 사이클이 발견되면 0을 출력하고, 사이클이 없으면 위상 정렬된 결과를 출력한다.

코드

#include <bits/stdc++.h>
using namespace std;

void dfs(int node, vector<vector<int>> &graph, vector<bool> &finish, vector<int> &visited, int &order, bool &isCycle) {
    if (isCycle) return;
    visited[node] = order++;

    for (int& next : graph[node]) {
        if (visited[next] == 0) {
            dfs(next, graph, finish, visited, order, isCycle);
        }
        else if (!finish[next]) {
            isCycle = true;
            return;
        }
    }
    finish[node] = true;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;

    vector<vector<int>> graph(n + 1);
    vector<int> depth(n + 1);
    vector<vector<int>> v(m);
    
    // 선후 관계 입력
    for (int i = 0; i < m; i++) {
        int size, prev; cin >> size >> prev;
        for (int j = 1; j < size; j++) {
            int node; cin >> node;
            graph[prev].push_back(node);
            depth[node]++;
            prev = node;
        }
    }

    vector<bool> finish(n + 1);
    vector<int> visited(n + 1);
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    int order = 0;
    
    // 진입 차수가 0인 노드를 우선 큐에 넣기
    for (int i = 1; i <= n; i++) {
        if (depth[i] == 0) {
            bool result = false;
            dfs(i, graph, finish, visited, order, result);
            if (result) {
                cout << 0 << '\n';  // 사이클이 있으면 0 출력
                return 0;
            }
            pq.push({ 0, i });
        }
    }

    vector<int> result;
    while (!pq.empty()) {
        int node, d; 
        tie(d, node) = pq.top();
        pq.pop();
        result.push_back(node);

        // 후속 노드들의 진입 차수 감소
        for (int& next : graph[node]) {
            if (--depth[next] == 0) pq.push({ depth[next], next });
        }
    }
    
    // 결과 출력
    for (int& node : result) cout << node << '\n';
}