[백준 2252] 줄 세우기 (C#, C++) - soo:bak

문제 링크

2252번 - 줄 세우기

설명

일부 학생들에 대한 키 비교 결과 A → B(A가 앞) 가 주어집니다. 전체 학생을 조건에 맞게 한 줄로 세우면 됩니다.
사이클이 없다고 가정하므로, 위상 정렬을 통해 아무거나 가능한 순서를 출력하면 됩니다.

접근법

• 인접 리스트와 진입 차수 배열을 구성합니다.
• 진입 차수 0인 학생을 큐에 넣어 BFS로 위상 정렬을 수행합니다.
• 큐에서 꺼낸 순서대로 출력하면 조건을 만족하는 한 가지 줄 세우기가 됩니다.
• N ≤ 32,000, M ≤ 100,000, O(N+M).

---

Code

C#

using System;
using System.Collections.Generic;

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

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

      for (int i = 0; i < m; i++) {
        var line = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        int a = line[0], b = line[1];
        adj[a].Add(b);
        indeg[b]++;
      }

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

      var sb = new System.Text.StringBuilder();
      while (q.Count > 0) {
        int cur = q.Dequeue();
        sb.Append(cur).Append(' ');
        foreach (int nxt in adj[cur]) {
          if (--indeg[nxt] == 0) q.Enqueue(nxt);
        }
      }

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

C++

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

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

  int n, m; cin >> n >> m;
  vector<vector<int>> adj(n + 1);
  vector<int> indeg(n + 1, 0);

  for (int i = 0; i < m; i++) {
    int a, b; cin >> a >> b;
    adj[a].push_back(b);
    indeg[b]++;
  }

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

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

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