[ 백준 2623 ] 음악 프로그램 (C++)

백준의 음악 프로그램(2623) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

가수들이 무대에 오를 순서를 구해야 하는 문제이다.

본인은 "일의 순서를 정렬시키는 알고리즘"인 위상정렬로 이 문제를 접근해 보았다.

각 PD들 마다 원하는 순서가 있고, 해당 순서들을 종합해서 위상정렬을 구현한다면 전체적인 순서를 구할 수 있기 때문이다.

"현재 A번 가수가 무대에 올랐다면, 그 다음에 무대에 오를 수 있는 가능성이 있는 가수" 를 찾는 과정을 보자

본인은 vector배열과 int형 배열 2개를 가지고 위의 과정을 진행해 주었다.

먼저, 선언한 int형 배열은 "나보다 우선적으로 무대를 진행해야 하는 가수의 수"를 저장해주었다. (int Entry[])

만약, Entry[a] = b 의 의미는 "a번 가수가 무대에 오르기 위해서는, b명의 가수가 무대를 이전에 진행해야 합니다" 를 의미한다.

vector배열은 "내가 무대를 진행함으로써, 이 후에 무대에 오를 가수에게 순위를 부여" 하는 것이라고 생각하면 된다.

다음과 같은 예시를 한번 봐보자. 가수가 총 4명 있고, 2명의 PD가 있다고 가정해보자.

1번 PD = { 1, 3, 4 }

2번 PD = { 2, 4 }

위와 같은 순서대로 PD들이 무대를 진행하길 원한다.

그렇다면 가장 먼저 무대에 오를 수 있는 사람은 누구일까 ?? 바로 '1번' 가수와 '2번' 가수 2명이 존재한다.

왜 ?? 1번 가수가 무대를 서기 위해서 이전에 무대를 서야 하는 사람은 존재하지 않는다.

마찬가지로 2번 가수도 똑같다. 하지만, 3번가수와 4번 가수같은 경우를 보자.

3번 가수 같은 경우에는 '1번'이 우선적으로 무대를 진행해야 하기 때문에 가장 먼저 무대에 절대 오를 수가 없다.

4번 가수 같은 경우에도 '1번, 2번, 3번' 이 우선적으로 무대를 진행해야 하기 때문에 가장 먼저 무대에 절대 오를 수가 없다.

위와 같은 관계를 vector배열에 저장해준 것이다. 위의 관계를 표현해보면 다음과 같이 표현할 수 있다.

vector[1] = { 3, 4 }

vector[2] = { 4 }

vector[3] = { 4 }

vector[4] = { }

위의 상태에서 Entry배열을 보면 { 0, 0, 1, 3 } 이 될 것이다.

즉 ! 가장 먼저 무대를 오를 수 있는 사람은 Entry 값이 0인 사람이 될 것이다.

만약 여기서 1번 사람이 무대를 했다면 ? 1번 사람 이 후에 무대를 할 가능성이 있는 사람인 '3번'사람과 '4번 사람'의

Entry값을 하나씩 없애주는 것이다. 왜 ? 이미 1번 사람 한명이 무대를 진행해 버렸기 때문이다.

즉, Entry배열이 { 0, 0, 0, 2 } 가 될 것이다.

이 후, 2번 가수가 진행했다면 ? Entry값이 { 0, 0, 0, 1 }, 3번 가수가 진행하게 되면 { 0, 0, 0, 0 } 이 될 것이다.

이러한 과정을 위상정렬이라고 한다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N, M;
int Entry[MAX];
vector<int> V[MAX];
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        vector<int> Temp;
        int Num; cin >> Num;
        for (int j = 0; j < Num; j++)
        {
            int a; cin >> a;
            Temp.push_back(a);
        }
        for (int j = 0; j < Temp.size(); j++)
        {
            for (int k = j + 1; k < Temp.size(); k++)
            {
                V[Temp[j]].push_back(Temp[k]);
                Entry[Temp[k]]++;
            }
        }
    }
}
 
void Solution()
{
    queue<int> Q;
    for (int i = 1; i <= N; i++)
    {
        if (Entry[i] == 0) Q.push(i);
    }
 
    vector<int> Answer;
    while (Q.empty() == 0)
    {
        int Num = Q.front();
        Q.pop();
        Answer.push_back(Num);
 
        for (int i = 0; i < V[Num].size(); i++)
        {
            int Next = V[Num][i];
            Entry[Next]--;
 
            if (Entry[Next] == 0) Q.push(Next);
        }
    }
    if (Answer.size() != N) cout << 0 << endl;
    else
    {
        for (int i = 0; i < Answer.size(); i++) cout << Answer[i] << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}