(C++) 백준 2188 축사 배정

문제 및 풀이

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

처음에는 백준 9576 책 나눠주기(https://velog.io/@minayeah/C-백준-9576-책-나눠주기) 처럼 생각해서 들어갈 수 있는 축사가 적은 소를 우선순위 높게 생각하고 그런 소부터 먼저 축사를 배정했다.
ㅠㅠ 하지만 생각해보면 허점이 많다;;;; 대표적으로 다음과 같은 반례이다.

5 4
2 2 5
2 3 5 
2 4 5
3 2 3 4

결국 다른풀이를 참고해서 풀었는데, 이렇게 제한된 항목을 최대한 많이 분배하는 문제는 이분매칭으로 분류되었다.

이분 매칭은 dfs를 사용해서 문제에서 주어진 것을 최대한 많이 분배하는 알고리즘이다. 핵심은 노드 x가 탐색한 공간이 비어있거나, 이미 공간을 차지하고 있는 다른 노드가 다른 공간에도 들어갈 수 있으면, 해당 공간은 노드 x가 들어갈 수 있다는 것이다. 이렇게 모든 노드에 대해 for문을 돌면서 배열(공간)을 갱신하면, 답을 구할 수 있다.

갓동빈 블로그의 이분매칭(https://blog.naver.com/ndb796/221240613074) 글을 참고해서 풀었다.

이분 매칭 코드

    
bool dfs(int x){

    for(int i=0; i<v[x].size(); i++){

        int now = v[x][i];
        if(home[now]) continue;
        home[now]=true;
		// 현재 탐색하는 축사 now가 비어있거나(d[now]==0)
        // 축사 안에 있는 소(d[now])가 다른 공간에도 들어갈 수 있다면(dfs(d[now])==true)
        // 소 x는 축사 d[now]에 들어갈 수 있다.
        if(d[now]==0 || dfs(d[now])){ 
            d[now]=x;
            return true;
        }
    }
    return false;
}

전체 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int N,M,x,y;
vector<int> v[205];
bool home[205];
int d[205];

bool dfs(int x){

    for(int i=0; i<v[x].size(); i++){

        int now = v[x][i];
        if(home[now]) continue;
        home[now]=true;

        if(d[now]==0 || dfs(d[now])){
            d[now]=x;
            return true;
        }
    }
    return false;
}




int main(){

    cin>>N>>M;

    for(int i=1; i<=N; i++){
        cin>>x;
        for(int j=0; j<x; j++){
            cin>>y;
            v[i].push_back(y);
        }
    }


    for(int i=1; i<=N; i++) {
        fill(home, home+M+1, false);
        dfs(i);
    }

    int ans=0;
    for(int i=1; i<=M; i++) {
        if(d[i]>0) ans++;
    }
    cout<<ans;

}