이분 매칭 (Bipartite Matching)

이분 매칭은 이분그래프에서의 매칭을 의미한다. HopcroftKarp 알고리즘을 이용하면 $O(E\sqrt{V})$에 풀 수 있지만, 여기서는 더 쉬운 알고리즘만을 다루겠다. DFS를 활용하면 $O(VE)$로 최대 이분 매칭을 구할 수 있다. 

 

참고.

- 일반 그래프에서의 매칭은 더 어려운 문제이다. blossom 알고리즘을 이용하면 $O(V^2E)$에 된다고 한다. 

- weighted bipartite matching은 MCMF를 활용하여 풀 수 있다.

 

DFS를 사용한 알고리즘은 상당히 간단하다. 이분 그래프를 $G=(L, R, E)$라 하자. $L, R$은 정점의 집합이다. $L$에 속한 정점을 차례대로 보면서 매칭을 추가해줄 것이다. $v \in L$에 대해 $v$와 연결된 정점 $u \in R$을 본다. $u$가 여태까지 구한 매칭에 속하지 않는다면 이어주면 된다. 이미 속한다면, $u$가 매칭으로 이어져있는 정점 $p$에 대해 $p-u$ 매칭을 끊고 $v-u$를 연결한다. 그 후 $p$에 대해 다시 매칭을 찾아본다. dfs로 이 과정을 반복한다. $p$에 대해 새로운 매칭을 찾는 것에 실패했다면, 다시 $p-u$를 연결해주고 다른 매칭을 찾아본다. dfs 과정에서 이미 지나온 정점에는 가지 않도록 해주어야 한다. 만약 dfs가 끝났는데도 새로운 매칭을 찾지 못했다면, 이 정점들로는 새로운 매칭을 찾을 수 없는 것이다. 이 과정을 $L$의 모든 정점에 대해 반복하면 된다.

 

아래 링크 참고.

https://jason9319.tistory.com/149

http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220807541506

https://www.crocus.co.kr/499

 

내 코드

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

vector<int> ed[MAXN];
int p[MAXN];					// R의 각 정점이 매칭된 L의 정점
bool chk[MAXN];					// L의 각 정점을 dfs 과정에서 이미 보았는가

bool f(int x) {
	if(x == -1) return true;
	if(chk[x]) return false;
	chk[x] = true;
	for(auto a : ed[x]) {
		int t = p[a];
		p[a] = x;			// 매칭을 끊고 뺐어온다
		if(f(t)) return true;		// 매칭 성공
		p[a] = t;			// 복구시킨다
	}
	return false;
}

int main() {
	//TODO
	memset(p, -1, sizeof(p));
	int ans = 0;
	for(int i = 1; i <= N; i++) {
		memset(chk, 0, sizeof(chk));
		if(f(i)) ans++;			// 매칭 성공
	}
	//TODO
}