백준 2623 음악 프로그램

작성일 | In |

Problem : 음악 프로그램

유형 : 위상정렬

문제 해석

  • 매니저가 정해준 순서에 맞춰 가수를 출력하라.
  • 불가능한 경우 0을 출력하라

문제 재해석

  • 선후관계를 유지하며 정렬해야 한다.
  • 위상 정렬 알고리즘 문제이다.
  • 사이클이 있는 경우 예외 처리를 해준다.

해결 전략

  • 위상 정렬을 통해 답을 구한다.
  • 사이클의 경우, 답 목록의 개수로 존재 여부를 판단한다.

설계, 구현

  • indegree 를 이용해 시작점이 될 수 있는지를 판별한다.
  • 시작점이 될 수 있는 경우 queue에 넣으면서 진행한다.

주의할 점

  • 없음

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;

int n, m;

vector<int> node[1002], answer;
queue<int> q;

int node_indegree[1002];


void Solve() {
    for (int i = 1; i <= n; ++i) {
        if (node_indegree[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        auto cur = q.front();   q.pop();
        answer.push_back(cur);

        for (const auto &nxt : node[cur]) {
            node_indegree[nxt]--;
            if (node_indegree[nxt] == 0) q.push(nxt);
        }
    }
    
    if ((int)answer.size() != n) {
        cout << 0 << "\n";
        return;
    }
    else {
        for (const int& ans : answer) {
            cout << ans << "\n";
        }
    }
}

void Manager_Input(int singer_n) {

    int front_singer, singer;
    for (int i = 0; i < singer_n; ++i) {
        cin >> singer;
        if (i == 0) {
            front_singer = singer;
            continue;
        }
        
        node[front_singer].push_back(singer);
        node_indegree[singer]++;
        front_singer = singer;
    }
}

void Input() {
    cin >> n >> m;

    int singer_n;
    while (m--) {
        cin >> singer_n;
        Manager_Input(singer_n);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • 없음