[백준 2623] 음악프로그램 (C#, C++) - soo:bak

문제 링크

2623번 - 음악프로그램

설명

보조 PD들이 각자 정한 가수 순서를 모두 만족하는 전체 출연 순서를 구하는 문제입니다. 순서를 만들 수 없으면 0을 출력합니다.

접근법

각 PD가 정한 순서에서 연속한 두 가수 사이에 선후 관계가 생깁니다. 예를 들어 순서가 3, 1, 2이면 3이 1보다 먼저, 1이 2보다 먼저 나와야 합니다. 이 관계들을 그래프의 간선으로 표현하면 위상 정렬 문제가 됩니다.

진입 차수가 0인 가수부터 큐에 넣고 하나씩 꺼내며 결과에 추가합니다. 꺼낸 가수와 연결된 가수들의 진입 차수를 1 감소시키고, 0이 되면 큐에 넣습니다.

모든 가수가 결과에 포함되면 순서대로 출력하고, 그렇지 않으면 사이클이 존재하므로 0을 출력합니다.

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var first = Console.ReadLine()!.Split();
      var n = int.Parse(first[0]);
      var m = int.Parse(first[1]);

      var adj = new List<int>[n + 1];
      for (var i = 1; i <= n; i++)
        adj[i] = new List<int>();
      var indeg = new int[n + 1];

      for (var i = 0; i < m; i++) {
        var line = Console.ReadLine()!.Split();
        var k = int.Parse(line[0]);
        var prev = 0;
        for (var j = 1; j <= k; j++) {
          var cur = int.Parse(line[j]);
          if (prev != 0) {
            adj[prev].Add(cur);
            indeg[cur]++;
          }
          prev = cur;
        }
      }

      var q = new Queue<int>();
      for (var i = 1; i <= n; i++) {
        if (indeg[i] == 0)
          q.Enqueue(i);
      }

      var order = new List<int>();
      while (q.Count > 0) {
        var u = q.Dequeue();
        order.Add(u);
        foreach (var v in adj[u]) {
          if (--indeg[v] == 0)
            q.Enqueue(v);
        }
      }

      if (order.Count != n)
        Console.WriteLine(0);
      else {
        foreach (var x in order)
          Console.WriteLine(x);
      }
    }
  }
}

C++

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

typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, M; cin >> N >> M;
  vvi adj(N + 1);
  vi indeg(N + 1, 0);

  for (int i = 0; i < M; i++) {
    int k; cin >> k;
    int prev = 0;
    for (int j = 0; j < k; j++) {
      int cur; cin >> cur;
      if (prev) {
        adj[prev].push_back(cur);
        indeg[cur]++;
      }
      prev = cur;
    }
  }

  queue<int> q;
  for (int i = 1; i <= N; i++) {
    if (indeg[i] == 0)
      q.push(i);
  }

  vi ans;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    ans.push_back(u);
    for (int v : adj[u]) {
      if (--indeg[v] == 0)
        q.push(v);
    }
  }

  if ((int)ans.size() != N)
    cout << 0 << "\n";
  else {
    for (int x : ans)
      cout << x << "\n";
  }

  return 0;
}