[알고리즘] 이분 매칭 알고리즘 (Bipartite Matching)

이분 매칭 알고리즘 (Bipartite Matching)

 

두 개의 정점 그룹이 존재할 때 모든 간선(경로)의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프를 이분 그래프(Bipartite Graph)라고 말합니다. 이러한 이분 그래프에서 예를 들어, 한쪽 그룹은 X 그룹, 다른 한쪽 그룹은 Y 그룹이라고 할 때 모든 경로의 방향은 X->Y인 그래프의 최대 유량을 구하는 것이 이분 매칭(Bipartite Matching)입니다.

 

이분 매칭을 통해 구하고자 하는 것은 최대 매칭 수입니다. 매칭을 한다는 것은 어떤 정점이 그것이 가리키는 위치의 다른 정점을 점유한 상태를 말하며 각 정점은 한 개씩만 점유 가능하고 여러개의 정점을 점유할 수 없습니다. 간선의 용량이 1인 것은 바로 이러한 이유에서입니다. 

 

알고리즘 원리

흐름도를 표현해보면 위와 같이 간선 용량이 1인 네트워크 플로우 문제로 이해할 수 있습니다. 다만, 이분 매칭은 깊이 우선 탐색(DFS)을 적용해 에드몬드 카프 알고리즘보다 좀 더 효율적인 복잡도를 구현할 수 있습니다.

간선의 방향은 반드시 왼쪽 -> 오른쪽이므로 생략하겠습니다. 우선, 정점 A는 정점 1을 점유할 수 있습니다. (총 매칭 수 : 1)

그 다음 정점 B는 정점 1을 점유하려고 합니다. 그런데 정점 A가 이미 정점 1을 보유하고 있으므로 A는 다른 정점을 점유하러 경로를 다시 찾습니다. 정점 3이 비어있으므로 A는 정점 3을 점유합니다. (총 매칭 수 : 2)

정점 C는 정점 5를 점유합니다. (총 매칭 수 : 3)

정점 D는 정점 3을 점유하려고 합니다. 그런데 정점 A가 이미 정점 3을 점유하고 있으므로 A가 다른 경로를 찾아 정점 1의 점유를 시도합니다. 그런데 정점 1 역시 정점 B가 점유하고 있으므로 B는 다른 경로를 찾아 비어있던 정점 2를 점유합니다. (총 매칭 수 : 4)

정점 E가 정점 2를 점유하려고 합니다. 그러나 정점 E는 더이상 매칭할 수 없습니다. 2를 점유하면 B가 경로를 다시 찾을 것이고 또 A가 다시 경로를 찾게되며 또 D가 다시 경로를 찾고 .. 등 계속해서 반복되기 때문에 매칭이 불가능합니다.

 

따라서 최종 매칭 수는 4가 됩니다.

 

알고리즘 구현

// Algorithm Analysis
// 이분 매칭 알고리즘 (Bipartite Matching)

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

using namespace std;
vector<int> vtx[MAX]; // 정점 vtx
int slt[MAX]; // vtx가 점유하고 있는 정점
bool done[MAX]; // 처리 여부
int n = 5; // 정점 수, 간선 수

bool dfs(int x) {
	// 연결된 모든 정점에 대해 들어갈 수 있는 지 시도
	for (int i = 0; i < vtx[x].size(); i++) {
		int p = vtx[x][i];
		// 이미 처리한 정점은 고려하지 않음
		if (done[p]) continue;
		done[p] = true;
		// 비어있거나 점유 정점에 더 들어갈 공간이 있는 경우
		if (slt[p] == 0 || dfs(slt[p])) {
			slt[p] = x;
			return true;
		}
		
	}
	return false;
}

int main() {
	vtx[1].push_back(1);
	vtx[1].push_back(3);
	vtx[1].push_back(5);
	vtx[2].push_back(1);
	vtx[2].push_back(2);
	vtx[3].push_back(5);
	vtx[4].push_back(3);
	vtx[5].push_back(2);
	
	int cnt = 0; // 매칭 수
	for (int i = 1; i <= n; i++) {
		fill(done, done + MAX, false);
		if (dfs(i)) cnt++;
	}
	printf("%매칭 %d번 성공\n", cnt);
	for (int i = 1; i < MAX; i++) {
		if (slt[i] != 0) {
			printf("%d => %d\n", slt[i], i);
		}
	}
}

 

시간 복잡도 : O(VE)

DFS를 적용한 이분 매칭 알고리즘의 시간 복잡도는 정점 수 * 간선 수 입니다.

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.