BOJ : 2188 축사 배정

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

기초적인 이분 매칭 문제이다.

백준 알고리즘의 이분 매칭문제는 앵간하면 다 아래의 프레임을 벗어나지 않고 해결 가능하다.

vector v = 소가 가고 싶어하는 축사, A[] = 소, B[] = 축사를 나타낸다.

소가 갈 수 있는 축사를 하나 선택하면 그 축사에 또 다른 소가 들어갈 수 있는지 확인하고 또 다른 소가 갈 수 있는 축사를 조사하는 것을 반복해서 만족하는 값이 가장 큰 것이 문제의 해답이 된다.

#include <cstdio>
#include <vector>
using namespace std;
 
int N,M,ans=0;
int A[202],B[202];
vector<int> v[202];
bool visited[202];
 
bool dfs(int start){
    visited[start]=1;
    //printf("start : %d\n",start+1);
    for(int &n : v[start]){
        if(B[n]==-1 || (!visited[B[n]] && dfs(B[n]))){
            A[start] = n;
            B[n] = start;
           // printf("소%d 축사%d\n",start+1, n+1);
            return true;
        }
    }
    return false;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0,S;i<N;i++){
        scanf("%d",&S);
        for(int j=0,s;j<S;j++){
            scanf("%d",&s);
            v[i].push_back(s-1);
        }
    }
    fill(A,A+N,-1);
    fill(B,B+M,-1);
    
    for(int i=0;i<N;i++){
        if(A[i]==-1){
            fill(visited, visited+N,false);
            if(dfs(i)) ans++;
        }
    }
    
    printf("%d\n",ans);
}