이분 매칭

이분 매칭 정리.

 

이분 매칭.

1. A그룹, B그룹 -> 두 개의 그룹으로 정점이 나뉘어져 있다.

2. A그룹의 정점들과 B그룹의 정점들을 '하나씩' 짝 지을때 (=이분 매칭) 가장 많이 짝 지을 수 있게 만드는 알고리즘.

 

이분 매칭 X , 정점들이 하나씩 짝 지어지지 않았음.

이분 매칭 O, 정점들이 하나씩 짝 지어짐.

 

방법.

1. A그룹의 첫번째 정점과 '연결 가능한' B그룹의 정점을 찾고 연결.  

2. A그룹의 다음 정점과(=A2) '연결 가능한' B그룹의 정점을 찾고, 해당 B그룹의 정점(=B1)이 A그룹의 정점 중 아무 정점과도 연결되어 있지 않다면 곧바로 연결.

 

 이미 연결되어 있다면 B그룹의 정점(=B1)과 연결된 A그룹의 정점(=A1)이 또 다른 연결 가능한 B그룹의 정점(=B2)이 있는지 찾는다.

 

 1) 연결 가능한 정점을 찾을 경우 : A1에서 현재 연결된 B그룹의 정점(=B1)을 포기하고 다른 정점(=B2)으로 연결. 이 후 A2정점과 B1정점이 연결된다.

 2) 연결 가능한 정점을 못찾을 경우 : A1에서 현재 연결된 B그룹의 정점(=B1)에서 다른 정점으로 옮길 수 없음으로 그대로 남고, A2 정점은 그 다음 '연결 가능한' B그룹의 정점(=B1을 제외한 다른 정점)을 찾는다. 

 

3. 1,2 번 과정을 반복하면서 A그룹의 끝 정점까지 완수.

현재 A1과 B1이 연결되있는 상태(은색 1선). A2가 B1가 '연결 가능한 상태'일 때 A1은 B2와도 연결 가능한 (은색 점선) 상태이기 때문에 B1에서 B2로 다시 연결되고 A2는 B1과 연결된다.(금색 2선)

 

코드.

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


using namespace std;


//그룹 A와 그룹 B의 정점들이 이어질 그래프.
vector<int> graph[MAX];

//그 중 이분매칭을 위한 match변수 
vector<int> match(MAX, 0);
//본문에 언급된 <방법> 2-1) & 2-2)에 해당하는 과정을 진행하기 위해 필요한 변수이다.
vector<bool> visited(MAX, 0);

int N=3, M=3;

bool dfs(int n) {
	//tmp = 그룹a 정점에서 (이분)매칭될 가능성이 있는 그룹b의 정점
	int tmp;
	for (int i = 0; i < graph[n].size(); ++i) {
		tmp = graph[n][i];

		//만약 이미 방문된 정점이라면 다음 연결될 수 있는 정점을 찾는다.
		if (visited[tmp]) continue;


		visited[tmp] = true;

		//이미 매칭된 그룹a의 정점이 없다면 n(그룹a의 정점)을 매칭
		//있다면 이미 매칭된 정점에서 이사갈 수 있는지 재귀함수로 확인.
		if (match[tmp] == 0 || dfs(match[tmp])) {
			match[tmp] = n;
			return true;
		}
	}
	return false;
}

int main() {
	graph[1].push_back(1);
	graph[1].push_back(2);
	graph[1].push_back(3);
	graph[2].push_back(1);
	graph[3].push_back(2);
	int count = 0;

	//첫 정점(start)부터 끝정점(N)까지
	for (int start = 1; start <= N; start++) {
    	//visited변수는 for문을 돌때마다 계속해서 초기화 된다.
        //그렇지 않으면 이전 for문에서 visitied의 원소가 true로 set된 정점을 pass하게 됨.
		visited = vector<bool>(MAX, 0);
        
        //이분 매칭이 이루어질 때 마다 count증가.
		if (dfs(start)) count++;
	}

	//이분 매칭된 정점들을 알아보기 위함.
	for (int i = 1; i <= M; i++) {
		if (match[i] != 0) {
			cout << "A그룹의 정점 :" << match[i] << " -> B그룹의 정점 : " << i << endl;
		}
	}
	
	cout << count << endl;

}

 

참조.

blog.naver.com/ndb796/221240613074

29. 이분 매칭(Bipartite Matching)

www.crocus.co.kr/499

이분 매칭 (Bipartite Matching)