이분 매칭(Bipartite Matching)

이분 매칭이란?

그래프중 특수한 그래프인 이분 그래프에서 두 그룹간의 최대 매칭을 의미한다.

이때 이분그래프는 전체 그래프에서 점 들을 두 그룹으로 나누었을 때, 같은 그룹내에는 간선이 존재하지 않게 나눌 수 있는 그래프를 의미한다.
보통 나눌 수 있는 경우가 여러가지기도 하지만, 문제에서 명확히 두 그룹을 분류해주는 경우가 많다.

예를 들어 왼쪽과 같은 이분그래프가 있다면 오른쪽 그림과 같이 3개의 매칭을 시켜 줄 수 있으므로 이분매칭의 값은 3이라고 할 수 있다. 그러면 어떠한 방식과 알고리즘으로 3이라는 값을 뽑아낼까?

호프크로프트라는 시간복잡도 $O(V\sqrt{E})$ 가 있지만 일단은 $O(VE)$알고리즘을 소개하려고 한다.

$O(VE)$ 알고리즘

이 알고리즘은 기본적으로 완전 탐색과 같은 느낌을 베이스로 깔고 진행한다. 각 왼쪽그룹의 노드를 순서대로 보면서, 그 노드와 어떤 노드를 매칭하면서 전체적인 매칭의 수를 추가할 수 있는지 확인하면서 진행이 된다.
일단 매칭을 시켜주고, 이미 매칭이 되어있는 노드면 그 노드와 매칭하고 있었던 노드를 다른애와 매칭시킬 수 있는지 계속 확인해 주는 방식이다. (굴러온 돌이 박힌들을 빼낸다!)
그림과 함께 설명하려고 한다. 

왼쪽의 이분 그래프에서 일단 A를 순서대로, 즉 a에 매칭을 시켜준다. 

왼쪽의 그림에서 B는 차례대로 확인을 한다.
a와 매칭하려고 했지만 a는 이미 A와 매칭되어있기 때문에 A를 다른곳에 매칭시킬 방법을 본다.
A가 a의 대체로 b와 매칭이 가능하기 때문에 A-b & B-a로 매칭을 완료한다. (1증가)

C도 차례대로 a와 매칭을 하려고 한다.
a는 B와 매칭되어있었으므로 B의 대체재를 찾는다.
B의 대체재로 b를 찾았지만 b는 A와 이미 매칭되어있다.
A의 대체재를 탐색하고 c가 있으므로 B는 b와 매칭이 가능하다.
B는 b라는 대체재가 있으므로 C는 a와 매칭을 할 수 있다.
결과적으로 총 매칭수가 1 증가

D는 차례대로 c와 매칭하려고 했지만 A는 대체재가 존재하지 않으므로 D가 밀려난다.
D는 그 다음인 d와 매칭하려고 하며, 할 수 있으므로 매칭을 하고 끝낸다.

결과적으로 오른쪽과 같은 매칭이 되고 4개의 매칭갯수가 생기며 이는 최대가 맞다.

코드

이분매칭의 거의 기본문제라고 할수 있는 BOJ 11375 열혈강호의 코드를 가져왔다.

코드는 https://jason9319.tistory.com/149 이분의 코드를 많이 참조했다. 전체적으로 코드가 깔끔하고, 설명하는바를 잘 나타내 준 코드다. 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
ll n,m;
ll vis[1010101];
ll mat[1010101];
vector<ll> edg[1010101];
ll ans;
bool bm(ll x)
{
    if(vis[x]) return false;
    vis[x]=1;
    for(auto pre:edg[x]){
        if(mat[pre]==0||bm(mat[pre])){
            mat[pre]=x;
            return true;
        }
    }
    return false;
}
 
int main()
{
    ll i,j,k,l,x;
    scanf("%lld %lld",&n,&m);
    for (i=1;i<=n;i++){
        scanf("%lld",&k);
        while (k--)
        {
            scanf("%lld",&x);
            edg[i].push_back(x);
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++) vis[j]=0;
        if(bm(i))ans++;
    }
    printf("%lld",ans);
    return 0;
}