이분 매칭 (Bipartite Matching)

---

아래 내용을 모두 확인하고 다음 링크를 확인하여

이분 매칭에 대해 조금 더 알아가셨으면 좋겠습니다.

이분 매칭(Bipartite Matching) 시간 단축 방법 :: http://www.crocus.co.kr/744

---

이분 매칭(Bipartite Matching)이란?

이분 그래프에서 A 그룹의 정점에서 B 그룹의 정점으로 간선을 연결 할 때,

A그래프의 하나의 정점이 B그래프 하나의 정점만 가지도록 구성된 것이 이분 매칭이다.

이분 그래프(Bipartite Graph)란?

이분 그래프 :: 정점을 두개의 그룹으로 나누었을 때, 

존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 의미한다.

그림을 통해 보자.

이 이분 매칭의 원리는 다음과 같다.

 우선 a1이 b1을 연결한다.

그다음 a2가 b1을 연결하는데 a1과 겹친다. 이때 a1으로 돌아와서 문제를 해결해야 한다.

다음과 같이 a1이 b2를 지정하도록 한다.

a3가 가리킬 수 있는 첫번째 정점인 b1을 가리키도록한다. 이때 또 a2와 충돌하므로 a2를 해결한다.

a2가 b2를 보도록 한다. 이때 또 a1과 충돌하니 a1이 또 연결할 수 있는 정점을 확인한다.

a1이 b4와 연결될 수 있다.

a4가 b3이랑 연결되며 이분 매칭이 종료된다.

이 내용을 코드로 나타내면 다음과 같다.

이 알고리즘을 이용한 문제를 접해보고 싶다면

http://programbasic.tistory.com/498 를 참조하길 바란다.

#include <iostream>
#include <vector>
 
using namespace std;
 
#define MAX_N 201
#define MAX_M 201
 
// A와 B의 정점의 개수
int n, m;
 
// adj[i][j] = Ai와 Bj가 연결되어 있는가?
bool adj[MAX_N][MAX_M];
 
// 각 정점에 매칭된 상대 정점의 번호를 지정한다.
vector<int> aMatch, bMatch;
 
// dfs()의 방문 여부
vector<bool> visited;
 
// A의 정점인 a에서 B의 매칭되지 않은 정점으로 가는 경로를 찾는다.
bool dfs(int a)
{
    if (visited[a])
        return false;
 
    visited[a] = true;
 
    for (int b = 0; b < m; b++)
    {
        if (adj[a][b])
        {
            // b가 매칭되어 있지 않다면 bMatch[b]에서부터 시작해 증가 경로를 찾는다.
            // 매칭되어 있다면 dfs에서 매칭되어있는 A정점이 다른 곳을 매칭 할 수 있는지 본다.
            if (bMatch[b] == -1 || dfs(bMatch[b]))
            {
                // 증가 경로를 발견하였을 때, a와 b를 매치시킨다.(이어준다.)
                aMatch[a] = b;
                bMatch[b] = a;
 
                return true;
            }
        }
    }
 
    return false;
}
 
// aMatch, bMatch 배열을 계산하고 최대 매칭 크기를 반환한다.
int bipartiteMatch()
{
    // -1로 초기화 (어떤 정점과도 연결되어 있지 않다는 의미)
    aMatch = vector<int>(n, -1);
    bMatch = vector<int>(m, -1);
 
    int size = 0;
 
    for (int start = 0; start < n; start++)
    {
        visited = vector<bool>(n, false);
 
        // 깊이 우선 탐색을 이용해 start에서 시작하는 증가 경로를 찾는다.
        if (dfs(start))
            size++;
    }
 
    return size;
}
 
int main()
{
    n = 4; // A 정점 수
    m = 4; // B 정점 수
 
    // A의 정점i와 B의 정점 j가 연결되어 있으면 1로 표시
    adj[0][0] = 1; // 1 == true (adj 타입이 bool)
    adj[0][1] = 1;
    adj[0][3] = 1;
 
    adj[1][0] = 1;
    adj[1][1] = 1;
 
    adj[2][0] = 1;
    adj[2][2] = 1;
 
    adj[3][2] = 1;
    adj[3][3] = 1;
 
    cout << bipartiteMatch() << endl;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>