[C/C++] 백준 #2623 음악프로그램(위상정렬)

이번 문제는 그래프 이론 중 위상정렬을 이용한 문제입니다.

위상정렬은 일의 선후 관계가 주어지는 경우 선후관계를 맞추어서 하나의 리스트로 만들게 됩니다.

하지만 그래프의 노드 중 연결되지 않은 노드가 있거나 순환(cycle)이 존재하면 답이 없을 수 있습니다.

 

TV music program

 

음악프로그램 문제는 문제 자체는 위상정렬과 동떨어져 보일 수 있지만, 문제를 잘 해석해서 이 문제가 위상정렬 문제임을 알아내는 것이 중요합니다.  그렇지 않다면, 꽤 어려운 문제가 될 수 있습니다.

 

문제의 출처입니다.

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

 

음악 프로그램에서 AD가 여러명이라고 하지만, 이 여러명의 AD들이 가져온 순서들을 병합(merge)하면 하나의 큰 유향 그래프(directed graph)가 됩니다.  분할된 그래프나 순환이 있는지는 위상정렬 알고리즘을 이용해서 풀다보면, 자연스럽게 알 수 있습니다.

 

위상정렬을 할 때에는 인입 간선의 수가 가장 중요합니다.  출발점은 인입 간선의 수가 0인 것에서 출발을 하니까요.  전 인입 간선이 0인 노드들을 큐(queue)에 넣어서 프로그램했지만, 스택(stack)을 사용하셔도 전혀 문제가 없습니다.  위상정렬의 결과는 다양하게 나올 수 있으며, 모두 순서만 맞으면 되는 것이기 때문에 어떤 자료구조를 이용해서 푸시던지 상관이 없습니다.  결과값을 저장하는 곳은 리스트를 이용했습니다.  순서에 맞게 결과를 넣어주시면 됩니다.

 

제가 작성한 소스입니다.

//----------------------------------------------------------
//    baekjoon #2623 - Music Program
//        - by Aubrey Choi
//        - created at 2020-01-22
//----------------------------------------------------------
#include <stdio.h>
#include <queue>
#include <vector>

int main()
{
    int n, m, i, p, s;
    static int c[1001];
    std::vector<int> adj[1001], r;
    std::queue<int> q;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d",&i);
        if(i==0) continue;
        scanf("%d",&p);
        while(--i)
        {
            scanf("%d",&s);
            adj[p].push_back(s);
            c[s]++; p=s;
        }
    }
    for(i=1;i<=n;i++) if(!c[i]) q.push(i);
    while(!q.empty())
    {
        s=q.front(); q.pop(); r.push_back(s);
        for(auto k:adj[s]) if(!(--c[k])) q.push(k);
    }
    if(r.size()!=n) { puts("0"); return 0; }
    for(auto k:r) printf("%d\n", k);
}