[백준 1766] 문제집 (C#, C++) - soo:bak

문제 링크

1766번 - 문제집

설명

N개의 문제를 풀어야 하는데, 일부 문제는 선행 관계가 있어서 특정 문제를 먼저 풀어야 합니다. 선행 관계를 지키면서 가능하면 쉬운 번호부터 푸는 순서를 구하는 문제입니다.

접근법

먼저 “지금 풀 수 있는 문제”를 정의합니다. 선행 문제가 없거나, 선행 문제를 모두 푼 문제가 지금 풀 수 있는 문제입니다.

다음으로 매 순간 지금 풀 수 있는 문제 중 번호가 가장 작은 것을 고릅니다. 최소 힙에 지금 풀 수 있는 문제들을 넣어두면, 항상 가장 작은 번호를 빠르게 꺼낼 수 있습니다.

이후 문제를 풀 때마다 그 문제를 선행 조건으로 가지던 문제들을 확인합니다. 선행 조건이 모두 해결되었으면 해당 문제도 힙에 추가합니다.

시간 복잡도는 O((N + M) log N)입니다.

---

Code

C#

using System;
using System.Collections.Generic;
using System.Text;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var first = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      var n = first[0];
      var m = 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 = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        var a = line[0];
        var b = line[1];
        adj[a].Add(b);
        indeg[b]++;
      }

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

      var sb = new StringBuilder();
      while (pq.Count > 0) {
        pq.TryDequeue(out var cur, out _);
        sb.Append(cur).Append(' ');
        foreach (var nxt in adj[cur]) {
          indeg[nxt]--;
          if (indeg[nxt] == 0)
            pq.Enqueue(nxt, nxt);
        }
      }

      Console.WriteLine(sb.ToString().TrimEnd());
    }
  }
}

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 a, b; cin >> a >> b;
    adj[a].push_back(b);
    indeg[b]++;
  }

  priority_queue<int, vi, greater<int>> pq;
  for (int i = 1; i <= n; i++) {
    if (indeg[i] == 0)
      pq.push(i);
  }

  ostringstream out;
  while (!pq.empty()) {
    int cur = pq.top(); pq.pop();
    out << cur << ' ';
    for (int nxt : adj[cur]) {
      if (--indeg[nxt] == 0)
        pq.push(nxt);
    }
  }

  string res = out.str();
  if (!res.empty() && res.back() == ' ')
    res.pop_back();
  cout << res << "\n";

  return 0;
}