Bipartite Match [c++]

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

 

 사람의 집단을 A, 노트북의 집단을 B라고 할 때 이를 그래프로 나타내면 아래와 같다.

 

 

 위와 같이 각 집단에 원하는 항목이 있을대 가장 효과적으로 매칭 시키는 알고리즘, 즉 최대 매칭(Max Matching)을 수행하는 알고리즘이다. 다시 말해서 모든 사람이 각각 노트 북을 선택하여 가장 많이 연결 되는 경우의 수를 찾는 것이다.

 

이는 용량(Capacity)가 1인 네트워크 플로우 문제로도 해석 할 수 있다, 다만 에드몬드 카프 알고리즘은 시간 복잡도가

O(V + E^2) 이기 때문에 이분매칭에 한해 더 빠르고 효율적인 DFS를 활용한 방법으로 구현 할 것이다.

 

1. 동빈은 A를 선택한다.

2. 태일은 A를 선택 해야하지만 이미 동빈이 선택해 있으므로, 동빈이 A를 제외한 다른 노트북을 선택할 수 있는지 찾아본다. 여기서는 다른 노트북 B를 선택 할 수 있으므로 동빈이 B, 태일이 A를 선택하도록 한다.

3. 한울은 B를 선택해야 하지만 이미 동빈이 선택해 있으므로, 위와 같은 방식으로 동빈이 C, 태일이 A, 한울이 B를 선택하도록 한다.

 

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

using namespace std;

vector<int> a[MAX];

bool c[MAX]; // 특정한 정점의 정보
int d[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() {
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); // dfs할 때마다 c 초기화
if (dfs(i)) count++;
cout << d[1] << d[2] << d[3] << endl;
}
cout << count << "개의 매칭이 이루어졌습니다." << endl;
for (int i = 1; i <= 100; i++) {
if (d[i] != 0) {
cout << d[i] << " -> " << i << endl;
}
}
}