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

문제링크 : https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, num;
int front, after;
vector<int>inDegree, result;
vector<vector<int>>graph;
queue<int>q;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> M;
        
    inDegree.resize(N+1); 
    graph.resize(N+1); 
        
    while(M--)
    {
        cin >> num;
        cin >> front;
        for(int i=0; i<num-1; i++)
        {
            cin >> after;
            graph[front].push_back(after);
            inDegree[after]++;
            front=after; //앞에와 교체
        }
    }
   

    for(int i=1; i<=N; i++) //진입차수가 0인 정점들을 큐에 삽입
    {
        if(inDegree[i]==0) q.push(i);
    }

    while(!q.empty()) //큐가 비면 사이클 발생이므로 종료
    {
        int cur = q.front(); //현재 방문 노드
        result.push_back(cur);
        q.pop();
        for(int i=0; i<graph[cur].size(); i++) //인접한 노드들의 진입 차수를 1씩 줄이고, 0이면 다시 큐에 삽입
        {
            int next = graph[cur][i];
            if(--inDegree[next]==0) q.push(next);
        }
    }

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

위상정렬 문제이다.

최근에 푼 위상정렬 문제와 다른 점은 입력 부분과 출력 부분이다.

입력 부분은 뒤에 숫자가 앞에 숫자에 기차처럼 이어서 붙어있는 경우이므로 이에 유의해야한다.

<예제 : 3 1 4 3>
graph[3] = {1, 4, 3} -> X
graph[3] = 1, graph[1] = 4, graph[4] = 3 -> O

 

또 출력 부분에서도 예외 처리가 필요하다.

문제에서 순서를 정하는 것이 불가능하다면 0을 출력하도록 했으므로,

순서를 담은 result 벡터의 사이즈가 N이 아니라면 사이클이 발생하여 순서 정하는 것이 불가능하다는 의미이므로 이때 0을 출력해주도록 한다.