백준 2188번 - 축사 배정

백준 2188번 - 축사 배정

https://www.acmicpc.net/problem/2188

문제

• 농부 John씨는 그의 소 축사를 갓 완성하였다.

• 축사 환경을 쾌적하게 유지하기 위해서, John씨는 축사를 N개의 칸으로 구분하여 두고, 한 칸에는 한 마리의 소만을 들어가도록 하였다.

• 첫 주에는 소들을 임의적으로 칸에 배정하여 축사를 운영하였으나, 곧 문제가 발생하게 되었다. 자신들이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다.

• 농부 John씨를 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오.

• 축사의 번호는 1부터 M까지 매겨져 있다고 한다.

입력

• 첫째 줄에 소의 마릿수 N과 축사의 개수 M이 주어진다. (1<=N<=200, 1<=M<=200)

• 둘째 줄부터 N개의 줄에는 N마리의 소들이 각자 들어가기 원하는 축사에 대한 정보가 주어진다.

• i번째 소가 들어가기 원하는 축사의 수 Si(0<=Si<=M)가 먼저 주어지고, 그 이후에 Si개의 축사 번호가 주어진다. 한 축사가 2번 이상 입력되는 경우는 없다.

출력

• 첫째 줄에 축사에 들어갈 수 있는 소 마릿수의 최대값을 출력한다.

접근

• 이분 매칭(Bipartite Matching) 문제

• DFS를 이용하여 풀 수 있다.

  1. 첫 번째 농부부터 연결 가능한 축사를 찾는다.

  2. 연결가능한 축사란, 어느 농부와도 연결되어 있지 않은 축사이거나, 축사에 이미 농부가 연결되어 있더라도 그 농부가 다른 축사로 연결 될 수 있다면 연결 가능하다.

  3. n번 반복하고 각 농부마다 연결 가능한 여부를 판단하여 카운트.

C++ Code

#include <vector>
#include <algorithm>
#include <cstdio>
​
using namespace std;
​
int n, m;
const int MAX = 201;
const int INF = 2e9;
bool visited[MAX];
int b[MAX];
vector<vector<int>> adj;
​
int dfs(int here) {
    if (visited[here]) {
        return 0;
    }
    visited[here] = true;
​
    for (int i = 0; i < adj[here].size(); i++) {
        int there = adj[here][i];
        if (!b[there] || dfs(b[there])) {
            b[there] = here;
            return 1;
        }
    }
​
    return 0;
}
​
int main() {
    scanf("%d %d", &n, &m);
    adj.resize(n + 1);
​
    for (int i = 1; i <= n; i++) {
        int t1, t2;
        scanf("%d", &t1);
        while (t1--) {
            scanf("%d", &t2);
            adj[i].push_back(t2);
        }
    }
​
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        fill_n(visited, MAX, false);
        if (dfs(i)) ans++;
    }
    printf("%d\n", ans);
​
    return 0;
}