이분 매칭(Bipartite Matching)

  이분 매칭은 네트워크 플로우 알고리즘과 연계되는 개념이다.

 

이분 매칭은 A 집단이 B 집단을 선택하는 방법에 대한 알고리즘이다.

 

  '사람'이라는 집단과 '노트북'이라는 두개의 집단이 등장합니다.

 

 

 

  효과적으로 매칭시켜준다는 말은 다시 말해 '최대 매칭(Max matching)'을 의미하는 것입니다. 모든 사람 각각이 노트북을 선택하여 가장 많이 연결되는 경우를 찾는 문제라고 볼 수 있습니다. 그림을 한번 다음과 같이 플로우로 표현해보도록 합시다. 네크워크 플로우와 정확히 일치하게 됩니다.

 

  위와 같이 이분 매칭 알고리즘은 네트워크 플로우로 표현할수 있습니다. 각 용량(Capactiy)를 1로 설정한 네트워크 플로우 문제를 이해할 수 있는 것입니다. 다만 우리가 이전에 공부했던 에드몬드 카프 알고리즘은 시간 복잡도가 O(V * E^2)였습니다. 이분 매칭에 한해 이것보다 더 빠르고 효율적인 알고리즘을 설계할 수 있습니다. 바로 단순한 형태의 깊이 우선 탐색(DFS)로 푸는 방법입니다.

 

#include <iostream>
#include <vector>
#define MAX 101

using namespace std;

vector<int> a[MAX];
int d[MAX];
bool c[MAX];
int n = 3, m;

// 매칭에 성공한 경우 True, 실패한 경우 False
bool dfs(int x) {
	// 연결된 모든 노드에 대해서 들어갈 수 있는 시도
	for(int i = 0; i < a[x].size(); i++) {
		int t = a[x][i];
		// 이미 처리한 노드는 더 이상 볼 필요가 없음
		if(c[t]) continue;
		c[t] = true;
		// 비어있거나 점유 노드에 더 들어갈 공간이 있는 경우
		if(d[t] == 0 || dfs(d[t])) {
			d[t] = x;
			return true;
		}
	}
	return false;
}

int main(void) {
	a[1].push_back(1);
	a[1].push_back(2);
	a[1].push_back(3);
	a[2].push_back(1);
	a[3].push_back(2);
	
	int count = 0;
	for(int i = 1; i <= n; i++) {
		fill(c, c + MAX, false);
		if(dfs(i)) count++;
	}
	printf("%d개의 매칭이 이루어졌습니다. \n", count);
	for(int i = 1; i <= 100; i++) {
		if(d[i] != 0) {
			printf("%d -> %d\n", d[i], i);
		}
	}
	return 0;
}

  깊이 우선 탐색(DFS)를 이용해 이분 매칭을 간단히 풀 때의 시간 복잡도는 O(V * E)입니다. 가장 빠른 속도의 알고리즘은 아니지만 구현이 가장 간단하고 쉽다는 점에서 알고리즘에서 대회에서 가장 많이 사용되고 있습니다.