[백준 11375] 열혈강호 (C#, C++) - soo:bak

문제 링크

11375번 - 열혈강호

설명

N명의 직원과 M개의 일이 있고, 각 직원은 자신이 할 수 있는 일 목록을 갖는 상황에서, 한 직원은 하나의 일만, 한 일은 한 직원만 맡을 수 있을 때, 처리할 수 있는 일의 최대 개수를 구하는 문제입니다.

접근법

먼저, 직원들을 왼쪽 집합, 일들을 오른쪽 집합으로 두고, 직원이 할 수 있는 일마다 간선을 연결하여 이분 그래프를 만듭니다. 이렇게 하면 최대한 많은 직원을 서로 다른 일에 일대일로 배정하는 문제가 됩니다.

다음으로, 각 직원마다 DFS로 배정 가능한 일을 찾습니다. 직원이 어떤 일을 맡으려 할 때, 그 일이 아직 배정되지 않았으면 바로 배정합니다. 이미 다른 직원이 맡고 있다면, 그 직원이 다른 일로 옮길 수 있는지 재귀적으로 확인합니다. 옮길 수 있다면 현재 직원이 그 일을 맡습니다.

예를 들어, 직원 A가 일 1, 2를 할 수 있고 직원 B가 일 1만 할 수 있는 상황에서, A가 먼저 일 1을 맡았더라도 B가 일 1을 요청하면 A가 일 2로 옮길 수 있으므로 둘 다 일을 맡을 수 있습니다.

이후, 모든 직원에 대해 이 과정을 반복하면 배정된 일의 총 개수가 답이 됩니다.

---

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) {
    foreach (var v in adj[u]) {
      if (visited[v]) continue;
      visited[v] = true;
      if (match[v] == 0 || 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]);

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

    for (var i = 1; i <= N; i++) {
      var parts = Console.ReadLine()!.Split();
      var cnt = int.Parse(parts[0]);
      for (var j = 0; j < cnt; j++)
        adj[i].Add(int.Parse(parts[j + 1]));
    }

    match = new int[M + 1];
      visited = new bool[M + 1];
    var ans = 0;
    for (var u = 1; u <= N; u++) {
      Array.Clear(visited, 0, M + 1);
      if (Dfs(u)) ans++;
    }

    Console.WriteLine(ans);
  }
}

C++

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

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

int N, M;
vvi adj;
vi match;
vi visited;

bool dfs(int u) {
  for (int v : adj[u]) {
    if (visited[v]) continue;
    visited[v] = 1;
    if (match[v] == 0 || dfs(match[v])) {
      match[v] = u;
      return true;
    }
  }
  return false;
}

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

  cin >> N >> M;
  adj.resize(N + 1);
  for (int i = 1; i <= N; i++) {
    int cnt; cin >> cnt;
    adj[i].resize(cnt);
    for (int j = 0; j < cnt; j++) cin >> adj[i][j];
  }

  match.resize(M + 1, 0);
  visited.resize(M + 1, 0);
  int ans = 0;
  for (int u = 1; u <= N; u++) {
    fill(visited.begin(), visited.end(), 0);
    if (dfs(u)) ans++;
  }
  cout << ans << "\n";

  return 0;
}