[백준 2191] 들쥐의 탈출 (C#, C++) - soo:bak

문제 링크

2191번 - 들쥐의 탈출

설명

N마리의 쥐와 M개의 땅굴이 평면 위에 있고, 쥐의 속도 V와 매가 도착하기까지의 시간 S가 주어질 때, 매에게 잡아먹히는 쥐의 최소 수를 구하는 문제입니다. 각 땅굴에는 한 마리의 쥐만 들어갈 수 있습니다.

접근법

먼저, 쥐가 땅굴까지 도망갈 수 있는 조건을 생각합니다. 쥐와 땅굴 사이의 거리가 S 곱하기 V 이하이면 시간 안에 도착할 수 있습니다. 예를 들어, 속도가 2이고 시간이 3이면 거리 6 이하인 땅굴로 도망갈 수 있습니다.

다음으로, 쥐들을 왼쪽 집합, 땅굴들을 오른쪽 집합으로 두고, 쥐가 도달 가능한 땅굴마다 간선을 연결하여 이분 그래프를 만듭니다. 이렇게 하면 최대한 많은 쥐를 서로 다른 땅굴에 일대일로 배정하는 문제가 됩니다.

이후, 각 쥐마다 DFS로 증대 경로를 찾아 가능한 많은 쥐를 땅굴에 배정합니다. 쥐가 어떤 땅굴을 선택하려 할 때, 그 땅굴이 비어 있으면 바로 배정합니다. 이미 다른 쥐가 배정되어 있다면, 그 쥐가 다른 땅굴로 옮길 수 있는지 재귀적으로 확인합니다. 옮길 수 있다면 현재 쥐가 그 땅굴을 차지합니다.

예를 들어, 쥐 A가 땅굴 1, 2에 도달 가능하고 쥐 B가 땅굴 1에만 도달 가능한 상황에서, A가 먼저 땅굴 1을 선택했더라도 B가 땅굴 1을 요청하면 A가 땅굴 2로 옮길 수 있으므로 둘 다 살 수 있습니다.

마지막으로, 배정된 쥐의 수가 도망간 쥐의 수이므로, 잡아먹히는 쥐의 수는 N에서 배정된 수를 뺀 값입니다.

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

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static List<int>[] adj = Array.Empty<List<int>>();
  static int[] match = Array.Empty<int>();
  static bool[] visited = Array.Empty<bool>();

  static bool Dfs(int u) {
    for (var i = 0; i < adj[u].Count; i++) {
      var v = adj[u][i];
      if (visited[v]) continue;
      visited[v] = true;
      if (match[v] == -1 || Dfs(match[v])) {
        match[v] = u;
        return true;
      }
    }
    return false;
  }

  static void Main() {
    var first = Console.ReadLine()!.Split();
    var N = int.Parse(first[0]);
    var M = int.Parse(first[1]);
    var S = int.Parse(first[2]);
    var V = int.Parse(first[3]);

    var rats = new double[N, 2];
    for (var i = 0; i < N; i++) {
      var s = Console.ReadLine()!.Split();
      rats[i, 0] = double.Parse(s[0]);
      rats[i, 1] = double.Parse(s[1]);
    }

    var holes = new double[M, 2];
    for (var i = 0; i < M; i++) {
      var s = Console.ReadLine()!.Split();
      holes[i, 0] = double.Parse(s[0]);
      holes[i, 1] = double.Parse(s[1]);
    }

    adj = new List<int>[N];
    for (var i = 0; i < N; i++) adj[i] = new List<int>();

    var limit2 = (double)S * V;
    limit2 *= limit2;
    for (var i = 0; i < N; i++) {
      for (var j = 0; j < M; j++) {
        var dx = rats[i, 0] - holes[j, 0];
        var dy = rats[i, 1] - holes[j, 1];
        var d2 = dx * dx + dy * dy;
        if (d2 <= limit2 + 1e-9) adj[i].Add(j);
      }
    }

    match = new int[M];
    Array.Fill(match, -1);

    var matched = 0;
    for (var i = 0; i < N; i++) {
      visited = new bool[M];
      if (Dfs(i)) matched++;
    }

    Console.WriteLine(N - matched);
  }
}

C++

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<double,double> pdd;

bool dfs(int u, const vvi& adj, vi& match, vector<char>& vis) {
  for (int v : adj[u]) {
    if (vis[v]) continue;
    vis[v] = 1;
    if (match[v] == -1 || dfs(match[v], adj, match, vis)) {
      match[v] = u;
      return true;
    }
  }
  return false;
}

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

  int N, M, S, V; cin >> N >> M >> S >> V;
  vector<pdd> rat(N), hole(M);
  for (int i = 0; i < N; i++) cin >> rat[i].first >> rat[i].second;
  for (int i = 0; i < M; i++) cin >> hole[i].first >> hole[i].second;

  double limit2 = (double)S * V;
  limit2 *= limit2;

  vvi adj(N);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      double dx = rat[i].first - hole[j].first;
      double dy = rat[i].second - hole[j].second;
      double d2 = dx*dx + dy*dy;
      if (d2 <= limit2 + 1e-9) adj[i].push_back(j);
    }
  }

  vi match(M, -1);
  int matched = 0;
  for (int i = 0; i < N; i++) {
    vector<char> vis(M, 0);
    if (dfs(i, adj, match, vis)) matched++;
  }

  cout << N - matched << "\n";

  return 0;
}