[2188] 축사 배정

문제 링크 : https://www.acmicpc.net/problem/2188

2188 - 축사 배정

본문

농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 $M$개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다.

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

농부 존을 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 $1$부터 $M$까지 매겨져 있다.

입력

첫째 줄에 소의 수 $N$과 축사의 수 $M$이 주어진다. ($1 \leq N, M \leq 200$)

둘째 줄부터 $N$개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. $i$번째 소가 들어가기 원하는 축사의 수 $S_i$ ($0 \leq S_i \leq M$)이 먼저 주어지고, 이후 $S_i$개의 축사 번호가 주어진다. 같은 축사 번호가 두 번 이상 주어지는 경우는 없다.

출력

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

제한

시간 제한	메모리 제한
2sec	128MB

---

풀이

소들의 집합이랑 축사 칸의 집합은 각 원소가 같을 수 없는 따로 분리된 집합이다. 그중에서 소가 원하는 칸 (그래프로 연결된 정점들) 을 서로 매칭시킬 때 만들 수 있는 최대 매칭 수를 구하는 문제이므로, 이 문제는 이분 매칭의 기본형 문제임을 알 수 있다.

그래서, 이분 매칭을 그대로 구현하면 풀 수 있는 연습형 문제.

• 참고 알고리즘 : 이분 매칭

코드

사용 언어 : C

최종 수정일 : 2023 / 6 / 27

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

#define MAX_IDX 200
int n, m;

bool matrix[MAX_IDX + 1][MAX_IDX + 2];
bool visit[MAX_IDX + 2];
int matched[MAX_IDX + 2];

bool dfs(int x) {
    for (int i = 1; i <= m; ++i) {
        if (matrix[x][i] == true) {
            if (visit[i] == true) {
                continue;
            }
            visit[i] = true;

            if (matched[i] == false || dfs(matched[i]) == true) {
                matched[i] = x;
                return true;
            }
        }
    }
    return false;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        int a;
        scanf("%d", &a);
        while (a--) {
            int b;
            scanf("%d", &b);
            matrix[i][b] = true;
        }
    }

    int retval = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            visit[j] = false;
        }

        if (dfs(i) == true) {
            ++retval;
        }
    }

    printf("%d", retval);
    return 0;
}