2623번 : 음악프로그램 [C++]

문제 링크

성공 여부(걸린 시간): 성공(38분 40초)

아이디어

이 문제는 주어진 가수들의 선후 관계를 만족하도록 전체 순서를 정하는 문제로,
기본적인 위상 정렬(Topological Sort) 개념을 그대로 적용하는 문제이다.

각 PD가 제시한 가수들의 순서는
A → B → C 와 같이 앞에 있는 가수가 반드시 뒤에 있는 가수보다 먼저 나와야 한다는 방향 그래프의 간선 정보로 해석할 수 있다.

따라서 모든 순서 정보를 간선으로 변환한 뒤,
진입 차수(indegree)를 기반으로 하는 Kahn 알고리즘 방식의 위상 정렬을 수행하면 된다.

1️. 그래프 구성

입력으로 주어지는 한 PD의 순서가

3 1 4 3

이라면,

이는

• 1 → 4
• 1 → 3
• 4 → 3

과 같은 관계를 의미한다.

즉, 앞에 등장한 가수는 뒤에 등장한 모든 가수보다 먼저 와야 하므로
앞선 모든 원소에서 현재 원소로 간선을 추가해주었다.

이와 동시에 각 노드의 진입 차수(front 배열) 를 증가시켜 위상 정렬 준비를 한다.

---

2️. 위상 정렬 수행

• 진입 차수가 0인 노드를 먼저 큐에 삽입

• 큐에서 하나씩 꺼내 결과 벡터에 추가

• 해당 노드에서 나가는 간선을 제거하면서

  • 연결된 노드의 진입 차수를 감소
  • 진입 차수가 0이 되면 큐에 삽입

이 과정을 큐가 빌 때까지 반복한다.

---

3️. 사이클 판별 (0을 출력해야 하는 경우)

만약 주어진 순서들이 서로 충돌한다면,
그래프 내부에 사이클(Cycle) 이 존재하게 된다.

사이클이 존재하면 위상 정렬 과정에서
어느 시점 이후 더 이상 진입 차수가 0인 노드가 생기지 않게 된다.

즉,

• 큐가 비었는데
• 아직 모든 노드를 방문하지 못한 상태가 된다.

따라서 최종적으로 만들어진 결과 벡터의 크기를 확인하여

• result.size() == N → 정상적인 순서 존재 → 결과 출력
• result.size() != N → 사이클 존재 → 0 출력

으로 처리하였다.

처음에는 그래프를 생성하면서 만약 양방향이 된다면 종료해주는 방식으로 했으나
사이클이 생기는 경우는 잡아내지 못하기에 이런 식으로 수정을 해주었다.

이 방식은 별도의 사이클 탐색을 하지 않아도
위상 정렬 과정 자체를 통해 자연스럽게 판별할 수 있다는 점이 핵심이다.

---

풀이 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<vector<int>> graph(N+1, vector<int>());
    vector<int> front(N + 1, 0);
    vector < bool > visited(N + 1, false);

    for (int i = 0; i < M; i++) {
        int singer_num;
        cin >> singer_num;
        vector<int> singers(singer_num, 0);
        for (int j = 0; j < singer_num; j++) {
            cin >> singers[j];
            if (j != 0) {
                for (int k = 0; k < j; k++) {
                    graph[singers[k]].push_back(singers[j]);
                    front[singers[j]]++;
                }
            }
        }
    }

    queue<int> q;
    for (int i = 1; i <= N; i++) {
        if (front[i]==0) {
            q.push(i);
            visited[i] = true;
        }
    }

    vector<int> result;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        result.push_back(cur);

        for (int x : graph[cur]) {
            if (visited[x]) {
                continue;
            }
            front[x]--;
            if (front[x] == 0) {
                q.push(x);
                visited[x] = true;
            }
        }
    }

    if (result.size() != N) {
        cout << 0;
        return 0;
    }

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

    return 0;
}