이분 매칭

정점을 두 개의 그룹으로 나누었을 때, 모든 간선의 끝점 두 개가 서로 다른 그룹에 속하게 만들 수 있는 그래프를 이분 그래프(Bipartite Graph)라고 합니다.

 

이분 그래프에서 간선들을 선택해 봅시다. 단, 모든 정점은 선택한 간선 중 단 하나의 간선에만 포함될 수 있습니다.

이 때 선택할 수 있는 간선(매칭)의 최대 개수를 구하는 문제를 이분 매칭(Bipartite Matching) 문제라고 합니다.

 

예를 들어 다음과 같은 이분 그래프에서,

최대 매칭은 4이고, 실해 중 하나는 다음과 같습니다.

 

https://www.acmicpc.net/problem/11375

11375번: 열혈강호

그럼 최대 이분 매칭을 찾는 방법에 대해 알아봅시다.

 

1. DFS를 이용한 방법

 

이분 그래프의 두 그룹을 각각 A, B 라고 합시다.

A에 속한 어떤 정점 \(v\)으로부터 시작하는 매칭 하나를 추가할 수 있는지 확인하려고 합니다. 어떻게 하면 될까요?

 

위에서 썼던 그래프로 해 봅시다.

 

우선 1번 정점에서, 연결된 간선 중 아무거나 하나 선택하면 매칭을 하나 만들 수 있습니다.

6번 정점을 선택해 매칭을 하나 만들어 줍시다.

 

다음으로 2번 정점을 봅시다. 유일한 간선은 6번 정점과 이어진 간선인데, 6번 정점은 이미 1번과 이어져 있어서 선택할 수 없습니다.

그러면 간선을 추가할 수 없는 걸까요?

 

 

2번 정점에서부터 시작해서, 다음과 같은 경로가 존재하는지 확인합시다.

 

선택하지 않은 간선 → 선택한 간선 → 선택하지 않은 간선 → ... → 선택하지 않은 간선

 

위 그래프의 경우에는 2 → 6 → 1 → 7 이라는 경로가 존재합니다.

이 경로에서, 원래 선택되지 않은 간선은 선택하고, 선택되었던 간선은 선택하지 않도록 바꿔줍시다.

 

이와 같은 경로를 증가 경로라고 하고, 증가 경로를 선택해 선택 여부를 뒤집으면 무조건 매칭 하나를 추가할 수 있습니다.

 

따라서 A그룹에 속한 각각의 정점에 대해, 증가 경로가 존재하는지 확인함으로써 최대 이분 매칭을 구할 수 있습니다.

증가 경로는 DFS로 쉽게 구할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, m;
vector <int> graph[1001];
 
int match[1001];
// 현재 각 일에 매칭된 직원 번호
 
int cache[1001];
bool DFS(int v)
{
    cache[v] = 1;
    for (int nv : graph[v])
    {
        if (cache[match[nv]]) continue;
        if (match[nv] == 0 || DFS(match[nv]))
        {
            // 증가 경로를 찾았다.
            match[nv] = v;
            return true;
        }
    }
 
    return false;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
    for (int a = 1; a <= n; a++)
    {
        int sz; cin >> sz;
        for (int i = 0; i < sz; i++)
        {
            int b; cin >> b;
            graph[a].push_back(b);
        }
    }
 
    int ans = 0;
    for (int a = 1; a <= n; a++)
    {
        memset(cache, 0, sizeof cache);
        if (DFS(a)) ans++;
    }
 
    cout << ans;
}

---

2. 홉크로프트-카프 알고리즘 (Hopcroft-Karp Algorithm)

 

대부분의 이분탐색 문제는 위의 방식으로 풀 수 있지만, 시간복잡도를 더 줄일 수 있습니다.

 

이분 그래프에서 증가 경로를 찾을 때, 각각의 정점에 대해 따로따로 찾기 때문에 최악의 경우 지금까지 봤던 경로들을 계속 뒤집는 상황이 발생하게 됩니다.

 

이런 상황을 방지하기 위해, 각 단계마다 찾을 수 있는 모든 증가 경로를 한번에 찾은다음, 한번에 뒤집으면 어떨까요?

 

주황색 간선이 지금까지 찾은 매칭입니다.

이 그래프에서 한번에 최대한 많은 증가 간선을 찾으려면 어떻게 해야 할까요?

 

현재 A그룹에 속해 있는 정점 중, 매칭에 속하지 않는 정점까지의 거리를 0이라고 합시다.

 

증가 간선을 만들기 위해서는

A그룹에서 B그룹으로 이동할 때에는 선택하지 않은 간선을,

B그룹에서 A그룹으로 이동할 때에는 선택한 간선을 이용해서만 이동할 수 있습니다.

 

이 규칙을 적용하면서 BFS로 그래프를 탐색하면, 다음과 같이 떨어진 거리를 얻을 수 있습니다.

 

그 다음은 일반적인 이분 매칭과 비슷합니다.

모든 정점으로부터 시작하는 증가경로를 찾을 수 있는지 탐색합시다.

단, 맨 마지막 간선을 제외하고는 거리가 1 차이가 나는 정점으로만 이동할 수 있고, 이 때 증가 경로로 사용된 정점은 다시 사용할 수 없습니다.

 

위의 그래프의 경우에는,

다음과 같은 2개의 증가 경로를 찾을 수 있고, 이 한 단계를 통해 한번에 2개의 매칭을 찾을 수 있게 됩니다.

 

이것을 더 이상 증가 경로를 찾을 수 없을 때까지 반복하면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, m;
vector <int> graph[1001];
 
int mA[1001], mB[1001];
int dist[1001];
 
void BFS()
{
    memset(dist, -1, sizeof dist);
    queue <int> q;
    for (int i = 1; i <= n; i++)
    {
        if (mA[i]) continue;
        q.push(i);
        dist[i] = 0;
    }
 
    while (!q.empty())
    {
        int v = q.front(); q.pop();
        for (int nv : graph[v])
        {
            if (!mB[nv]) continue;
            if (dist[mB[nv]] != -1) continue;
            dist[mB[nv]] = dist[v] + 1;
            q.push(mB[nv]);
        }
    }
}
 
bool DFS(int v)
{
    for (int nv : graph[v])
    {
        if (!mB[nv] || dist[v] + 1 == dist[mB[nv]] && DFS(mB[nv]))
        {
            // 증가 경로를 찾았다.
            mA[v] = nv;
            mB[nv] = v;
            return true;
        }
    }
    return false;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
    for (int a = 1; a <= n; a++)
    {
        int sz; cin >> sz;
        for (int i = 0; i < sz; i++)
        {
            int b; cin >> b;
            graph[a].push_back(b);
        }
    }
 
    int ans = 0;
    while (true)
    {
        BFS();
 
        int res = 0;
        for (int i = 1; i <= n; i++)
        {
            if (mA[i]) continue;
            if (DFS(i)) res++;
        }
 
        if (!res) break;
        ans += res;
    }
 
    cout << ans;
}

 

홉크로프트-카프를 이용하면 많아도 \(\sqrt V\)번의 단계로 최대 이분 매칭을 찾을 수 있음이 증명되어 있습니다.

BFS와 DFS는 \(O(E)\)이므로, 총 시간복잡도는 \(O(\sqrt V E)\)입니다.

---

이분 매칭으로 풀 수 있는 문제들

 

 

1. 최소 정점 커버(Minimum Vertex Cover)

 

어떤 그래프에서 정점들을 선택했을 때, 그래프의 모든 간선이 선택한 정점과 연결되어 있다면 이것을 정점 커버라고 합니다.

이 때, 최소한의 정점을 이용해 정점 커버를 만드는 문제를 최소 정점 커버라고 합니다.

 

쾨닉의 정리에 의해, 이분 그래프에서 최소 정점 커버를 만드는데 필요한 정점의 개수는 최대 이분 매칭의 수와 같습니다.

 

 

2. 최대 독립 집합(Maximum Independent Set)

 

어떤 그래프에서 정점들을 선택했을 때, 선택한 정점들이 서로 인접해 있지 않다면 이것을 독립 집합이라고 합니다.

이 때, 최대한의 정점을 이용해 독립 집합을 만드는 문제를 최대 독립 집합이라고 합니다.

 

최소 정점 커버의 여집합이 최대 독립 집합입니다.

따라서 정점의 총 개수와 최대 이분 매칭으로 계산한 최소 정점 커버를 알면, 최대 독립 집합의 크기도 계산할 수 있습니다.

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

www.acmicpc.net/group/7712

ANZ1217