[백준 4792] 레드 블루 스패닝 트리 (C#, C++) - soo:bak

문제 링크

4792번 - 레드 블루 스패닝 트리

설명

빨간색과 파란색으로 칠해진 간선들이 주어질 때, 파란 간선을 정확히 k개 포함하는 스패닝 트리가 존재하는지 판별하는 문제입니다.

접근법

스패닝 트리에 포함될 수 있는 파란 간선 개수의 최솟값과 최댓값을 구합니다. k가 이 범위 안에 있으면 가능하고, 범위 밖이면 불가능합니다.

이 방법이 성립하는 이유는 간선 교환의 성질 때문입니다. 파란 간선이 최소인 스패닝 트리에서 시작해서, 트리에 없는 파란 간선을 하나 추가하면 사이클이 생깁니다. 이 사이클에서 빨간 간선을 하나 제거하면 다시 스패닝 트리가 되면서 파란 간선이 하나 늘어납니다. 이 과정을 반복하면 최솟값에서 최댓값까지 모든 개수를 만들 수 있습니다.

최솟값을 구하려면 파란 간선에 가중치 1, 빨간 간선에 가중치 0을 부여하고 최소 스패닝 트리를 만듭니다. 크루스칼 알고리즘에서 가중치가 작은 간선부터 선택하므로 빨간 간선이 우선적으로 선택되어 파란 간선이 최소화됩니다.

최댓값을 구하려면 같은 가중치를 사용하되, 가중치가 큰 간선부터 선택합니다. 파란 간선이 우선적으로 선택되어 파란 간선이 최대화됩니다.

k가 최솟값 이상이고 최댓값 이하이면 1을, 아니면 0을 출력합니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  struct Edge { public int w, u, v; }

  static int[] parent = new int[1001];
  static int Find(int x) => parent[x] == x ? x : parent[x] = Find(parent[x]);
  static bool Union(int a, int b) {
    a = Find(a); b = Find(b);
    if (a == b) return false;
    parent[b] = a;
    return true;
  }

  static int Kruskal(List<Edge> edges, int n) {
    for (var i = 1; i <= n; i++) parent[i] = i;
    var cnt = 0;
    var sum = 0;
    foreach (var e in edges) {
      if (Union(e.u, e.v)) {
        sum += e.w;
        if (++cnt == n - 1) break;
      }
    }
    return sum;
  }

  static void Main() {
    while (true) {
      var parts = Console.ReadLine()!.Split();
      var n = int.Parse(parts[0]);
      var m = int.Parse(parts[1]);
      var k = int.Parse(parts[2]);
      if (n == 0 && m == 0 && k == 0) break;

      var edges = new List<Edge>(m);
      for (var i = 0; i < m; i++) {
        var line = Console.ReadLine()!.Split();
        var w = line[0] == "B" ? 1 : 0;
        var u = int.Parse(line[1]);
        var v = int.Parse(line[2]);
        edges.Add(new Edge { w = w, u = u, v = v });
      }

      edges.Sort((a, b) => a.w.CompareTo(b.w));
      var minB = Kruskal(edges, n);

      edges.Sort((a, b) => b.w.CompareTo(a.w));
      var maxB = Kruskal(edges, n);

      Console.WriteLine(minB <= k && k <= maxB ? 1 : 0);
    }
  }
}

C++

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

struct Edge { int w, u, v; };
int parent[1001];

int findSet(int x) { return parent[x] == x ? x : parent[x] = findSet(parent[x]); }
bool unite(int a, int b) {
  a = findSet(a); b = findSet(b);
  if (a == b) return false;
  parent[b] = a;
  return true;
}

int kruskal(vector<Edge>& edges, int n) {
  for (int i = 1; i <= n; i++) parent[i] = i;
  int cnt = 0, sum = 0;
  for (auto &e : edges) {
    if (unite(e.u, e.v)) {
      sum += e.w;
      if (++cnt == n - 1) break;
    }
  }
  return sum;
}

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

  while (true) {
    int n, m, k; cin >> n >> m >> k;
    if (n == 0 && m == 0 && k == 0) break;
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
      char c; int u, v; cin >> c >> u >> v;
      edges[i].w = (c == 'B') ? 1 : 0;
      edges[i].u = u; edges[i].v = v;
    }

    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; });
    int minB = kruskal(edges, n);

    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w > b.w; });
    int maxB = kruskal(edges, n);

    cout << ((minB <= k && k <= maxB) ? 1 : 0) << "\n";
  }

  return 0;
}