[백준/Baekjoon] 2623 음악프로그램 C++ :: Topological Sort

https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

---

1. Logic

각 PD들이 뽑은 가수의 순서대로 공연순서를 정하는 것이기 때문에 순서를 정할 때 사용하는 위상 정렬을 사용할 수 있다.

 

처음 입력을 받을 때만 잘 받아주면 어려움 없이 풀 수 있다.

 

테스트케이스를 예시로 보면

1 > 4 > 3 순서대로 받아줘야 하기때문에

1 > 4

4 > 3 끊어서 입력받아줘야 한다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, m;

int inDegree[1001];
vector<int> input[1001];
vector<int> ans;

void topologicalSort() {
    queue<int> q;

    for(int i = 1; i <= n; i++) {
        if(!inDegree[i])
            q.push(i);
    }

    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        ans.push_back(cur);

        for(int i = 0; i < input[cur].size(); i++) {
            int next = input[cur][i];
            inDegree[next]--;

            if(!inDegree[next]) {
                q.push(next);
            }
        }
    }
}

int main() {
    cin >> n >> m;

    for(int i = 0; i < m; i++) {
        int cur;
        int prev;
        cin >> cur;
        cin >> prev;
        for(int j = 0; j < cur - 1; j++) {
            int a;
            cin >> a;
            input[prev].push_back(a);
            inDegree[a]++;
            prev = a;
        }
    }

    topologicalSort();

    if(ans.size() != n) {
        cout << 0;
    }
    else {
        for(int i = 0; i < n; i++) {
            cout << ans[i] << "\n";
        }
    }
}

 

 

---

3. Feedback

기본적인 위상정렬 문제였던 것 같다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90