[백준 / BOJ] C++ 2623 음악프로그램

2623번: 음악프로그램

 

문제

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

2623번: 음악프로그램

 

 

풀이

여러 가지 순서를 모두 만족하며 정렬해야 하므로 위상정렬 알고리즘을 사용한다. 기본적인 위상정렬 알고리즘을 배울 때 푸는 문제다. 각 순서를 입력받을 때마다 [앞->뒤]의 간선을 추가하고 뒤의 인덱스의 indegree 배열의 값을 1 증가시킨다.

 

indegree 배열의 값이 0인 정점을 모두 큐에 추가하고 차례대로 front 원소에 대해 탐색한다. front 원소를 ans 배열에 추가하고 front에서 향하는 정점들에 대해 indegree 값을 1 감소시키고 0이 되면 큐에 push 해 준다. 위 과정을 N번 반복하기 전에 큐가 비어있게 되면 사이클이 생겨 순서를 정할 수 없으므로 0을 출력하고 종료한다. 이외의 경우에는 마지막에 ans 배열의 값을 모두 출력한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M;
  vector<int> edge[1001], inDegree(1001, 0), ans;
  cin >> N >> M;
  while (M--) {
    int K, u, v;
    cin >> K;
    if (K == 0)
      continue;
    cin >> u;
    while (--K) {
      cin >> v;
      inDegree[v]++;
      edge[u].push_back(v);
      u = v;
    }
  }
  queue<int> q;
  for (int i = 1; i <= N; i++)
    if (inDegree[i] == 0)
      q.push(i);
  for (int i = 1; i <= N; i++) {
    if (q.empty()) {
      cout << 0;
      return 0;
    }
    int node = q.front();
    q.pop();
    ans.push_back(node);
    for (int next : edge[node])
      if (--inDegree[next] == 0)
        q.push(next);
  }
  for (int e : ans)
    cout << e << '\n';
  return 0;
}