[2623번] 음악프로그램

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 위상 정렬(Topological Sort) :: http://www.crocus.co.kr/716

이 문제는 아래 소스 코드에서 모든 설명을 해 두었습니다.

위상 정렬의 가장 기초적인 문제에 해당합니다. 

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
 
using namespace std;
 
vector<int> vc[1001]; // 그래프 형성을 위한 벡터
int line[1001]; // 자신에게 들어오는 간선들의 수
int result[1001]; // 최종 위상 정렬 결과 값
 
int main()
{
    int n, m;
 
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < m; i++)
    {
        int num, cur, prev;
 
        scanf("%d", &num);
 
        // 피디가 선호하는 순서가 없다면
        if (num == 0)
            continue;
 
        // prev를 먼저 담아주고 num - 1만큼 반복한다.
        scanf("%d", &prev);
        for (int j = 0; j < num - 1; j++)
        {
            scanf("%d", &cur);
 
            // cur은 prev에 의해 들어오는 간선이 생기므로 +1
            line[cur]++;
            // prev -> cur의 그래프가 생기는 과정
            vc[prev].push_back(cur);
            // cur이 다음 for문에서 prev가 된다.
            prev = cur;
        }
    }
 
    queue<int> q;
 
    // 들어오는 간선이 없는 정점은 모두 queue에 담아준다.
    for (int i = 1; i <= n; i++)
        if (line[i] == 0)
            q.push(i);
 
    // 위상 정렬
    for (int i = 0; i < n; i++)
    {
        // 위상 정렬 도중에 큐가 비게 된다면 위상 정렬을 할 수 없다.
        if (q.empty())
        {
            printf("0");
            return 0;
        }
 
        // 큐의 front를 cur로 받아준다.
        int cur = q.front();
        q.pop();
 
        // 큐에서 front 순서대로가 위상 정렬의 결과 값이다.
        result[i] = cur;
 
        // cur->next로 연결되는 노드들에 대해 아래 코드를 수행한다. 
        for (int j = 0; j < vc[cur].size(); j++)
        {
            int next = vc[cur][j];
            // cur->next의 간선을 지우는 과정, 이때 간선의 수가 0이 되면 큐에 담아준다.
            if (--line[next] == 0)
                q.push(next);
        }
    }
 
    // 위상 정렬 결과 값을 출력한다.
    for (int i = 0; i < n; i++)
        printf("%d\n", result[i]);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>