백준 2623번 [음악프로그램](C++) -yes6686- 티스토리

백준 문제 풀이: 2623 [음악프로그램]

---

문제 링크: https://www.acmicpc.net/problem/2623

문제 설명:

음악 프로그램에서 특정 가수들의 순서를 정해야 합니다. 각 PD는 자신이 정한 순서대로 가수들을 정렬하고자 하며, 이를 기반으로 전체 순서를 출력합니다. 순서를 정할 수 없는 경우 0을 출력합니다.

---

문제 해결 코드

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

int arr[1001];
int inDegree[1001];
vector<int>v[1001];
queue<int>q;
queue<int>result;

int main() {
    int n, m;
    cin >> n >> m;
    int w;
    for (int i = 0; i < m; i++) {
        cin >> w;
        for (int j = 0; j < w; j++) {
            cin >> arr[j];
        }
        for (int j = 1; j < w; j++) {
            v[arr[j - 1]].push_back(arr[j]);
            inDegree[arr[j]]++;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) q.push(i);
    }
    for (int i = 1; i <= n; i++) {
        if (q.empty()) {
            cout << 0 << endl;
            return 0;
        }
        int k = q.front();
        q.pop();
        result.push(k);
        for (int j = 0; j < v[k].size(); j++) {
            int next = v[k][j];
            inDegree[next]--;
            if (inDegree[next] == 0) q.push(next);
        }
    }
    while (!result.empty()) {
        int k = result.front();
        result.pop();
        cout << k << '\n';
    }
}

예제

입력:
6 3
3 1 4 3
4 6 2 5 4
2 3 6

출력:
1
4
6
2
5
3

---

코드 설명

• 입력 처리:
  • 각 PD가 제시한 순서를 입력받아 그래프의 간선과 진입 차수를 설정합니다.
• 위상 정렬:
  • 진입 차수가 0인 노드를 큐에 넣고, 해당 노드에서 나가는 간선을 처리합니다.
  • 큐가 비게 되면 순서를 정할 수 없는 경우이므로 0을 출력하고 종료합니다.
• 결과 출력:
  • 큐에서 꺼낸 노드를 순서대로 출력하여 최종 정렬된 결과를 반환합니다.

시간 복잡도

• 간선의 처리: O(m)
• 위상 정렬: O(n + m)
• 총 시간 복잡도: O(n + m)

---

결과

위 코드는 입력된 조건에 따라 올바른 순서를 출력하며, 입력 조건에서 모순이 있거나 순서를 정할 수 없는 경우 0을 반환합니다.