이분 매칭(Bipartite Matching)

네트워크 플로우의 개념중에서 이분 그래프(bipartite grape)에서의 최대 유량을 구하는 경우를 이분 매칭이라고 부릅니다.

이분 그래프는 다음과 같은 모양을 띄고 있습니다.

위의 그림에서 파란색 정점과 노란색 정점들 끼리는 어떠한 간선도 존재하지 않습니다.

이렇게 정점을 두 그룹으로 나누었을 때 모든 간선에 연결 된 두 정점이 서로 다른 그룹에 존재하는 그래프를 이분 그래프라고 합니다.

간선의 용량이 전부 1인 이분 그래프에서의 최대 유량을 구하는 문제는 이분 그래프에서의 최대 매칭과 동치입니다. 

이분 그래프에서 매칭이라는 말은 서로 다른 그룹에 놓인 두 정점을 짝지어주는 의미이고

우리는 이분 그래프에서 최대 매칭을 최대 유량 알고리즘인 디닉이나 에드몬드 카프 알고리즘을 이용하여 구해줄 수 있겠지만 

이분 매칭에 한해서 HopcroftKarp Algorithm을 이용하며 O(E*sqrt(V))라는 상대적으로 매우 빠른 시간 복잡도로 구할 수 있습니다.

하지만 이 글에서 소개하려는 방법은 이 방법은 아니고 DFS를 이용하여 이분 매칭을 O(V*E)의 시간에 좀 더 쉽게 구현하는 방법입니다.

자 그럼 어떤 과정을 통하여 매칭이 이루어지는지 확인해 보겠습니다.

우선 1번 정점에서 DFS를 실행하여 처음 방문하는 A번 정점과 매칭해줍니다. 자 이렇게 우선 (1-A)가 매칭이 되었습니다. 현재 매칭 수는 1이 되겠군요.

그 다음에 2번 정점에서 DFS를 실행하는데 A번 정점은 이미 1번 정점과 매칭 되어 있습니다.

그러면 우리는 다시 1번 정점으로 돌아가서 A번 정점 이외에 매칭 가능한 정점이 있다면 대신 매칭해 줍니다.

자 그러면 1번 정점은 이제 B번 정점과 매칭이 되겠군요. 그러면 자연스럽게 A번 정점의 매칭이 없어지므로 2번 정점과 A번 정점을 매칭해줍니다.

매칭은 위와같은 그림이 될 것입니다. 이 때 만약에 1번과 B번을 연결하는 간선이 존재하지 않았다면 2번 정점은 매칭에 실패하였을 것 입니다.

자 이제 다시 3번 정점에서 매칭을 해보겠습니다.

먼저 B번 정점은 이미 1번 정점과 매칭이 되어있으니 다시 1번 정점에서 탐색을 하여 매칭 가능한 정점을 확인합니다.

1번 정점에는 더 이상 매칭 가능한 정점이 존재하지 않으므로 그대로 (1-B)번 정점은 매칭이 됩니다.

3번 정점에서 매칭가능한 다음 정점을 탐색하여 C번 정점을 발견합니다. C번 정점은 아직 매칭이 되지 않았으니 3번 정점과 매칭시켜줍니다.

현재 최대 매칭은 3이 되겠군요.

자 이제 4번 정점에서 DFS를 돌리면 D번 정점을 발견하여 D번 정점과 매칭이 됩니다.

자 이제 마지막으로 5번 정점에서 DFS를 돌립니다. C번 정점은 이미 3번 정점과 매칭이 되있으므로 3번 정점에서 탐색합니다. 하지만 3번 정점도 더 이상 매칭할 정점이 없으므로 3-C번 정점이 그대로 매칭 된 채 5번 정점은 매칭에 실패합니다.

이렇게 매칭이 종료되고 최대매칭은 4가 됩니다.

#define MAX_N 1001
int n, m;
int visited[MAX_N];
int b[MAX_N];
vector<vector<int>> node;
int dfs(int here) {
    if (visited[here]) return 0;    //방문 된 정점은 매칭 불가
    visited[here] = 1;
    for (int i = 0; i<node[here].size(); i++) {
        int there = node[here][i];        
        if (!b[there] || dfs(b[there])) {    //매칭이 되어있지 않은 정점을 만나거나 이미 매칭된 정점이 다른 정점과 매칭이 가능할 때
            b[there] = here;        //매칭 시켜준 뒤 1을 리턴 해줌
            return 1;
        }
    }
    return 0;
}
int bmatch() {
    int ret = 0;
    for (int i = 1; i <= n; i++) {        //모든 정점에 대하여 매칭을 시도
        memset(visited, 0, sizeof(visited));
        if (dfs(i))ret++;
    }
    return ret;
}

소스코드는 다음과 같습니다. 기존 유량 알고리즘과 비교하면 상당히 간단한 편입니다.

마지막으로 이분매칭 기본 문제인 BOJ 11375 열혈강호 코드와 함께 글을 마치겠습니다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int n, m;
int visited[1010];
int b[1010];
vector<vector<int>> node;
int dfs(int here) {
    if (visited[here]) return 0;
    visited[here] = 1;
    for (int i = 0; i<node[here].size(); i++) {
        int there = node[here][i];
        if (!b[there] || dfs(b[there])) {
            b[there] = here;
            return 1;
        }
    }
    return 0;
}
int bmatch() {
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        memset(visited, 0, sizeof(visited));
        if (dfs(i))ret++;
    }
    return ret;
}
int main()
{
    scanf("%d%d", &n, &m);
    node.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        int v, x;
        scanf("%d", &v);
        while (v--) {
            scanf("%d", &x);
            node[i].push_back(x);
        }
    }
    printf("%d", bmatch());
    return 0;
}

자 이제 이분 매칭과 관련 된 여러 문제들을 풀어봅시다.