이분 매칭

이분 매칭 문제

정점이 두 그룹 \(L, R\)로 나뉘고 간선이 그룹 사이에만 있는 이분 그래프에서,
한 정점이 최대 한 간선에만 속하도록 고른 간선 집합을 매칭이라 한다.
간선을 최대한 많이 고르는 것이 최대 이분 매칭이다. "지원자–직무", "행–열"
처럼 서로 짝짓는 문제의 추상화다.

증가 경로 (augmenting path)

매칭되지 않은 \(L\)의 정점에서 출발해, 안 쓴 간선 → 쓴 간선 → 안 쓴 간선 → ...
을 번갈아 따라가 매칭되지 않은 \(R\)의 정점에서 끝나는 경로를 증가 경로라
한다. 이 경로에서 쓰임/안 쓰임을 뒤집으면 매칭 크기가 정확히 1 늘어난다(경로의
양 끝이 자유 정점이라 안 쓴 간선이 쓴 간선보다 하나 많기 때문).

베르주 정리: 매칭이 최대다 ⟺ 증가 경로가 더 이상 없다.

따라서 "각 왼쪽 정점에서 증가 경로를 찾아 매칭을 1씩 늘리는" 단순 알고리즘이
최대 매칭을 보장한다. 이것이 헝가리안 증가법(쾨니그식 DFS) 이다.

쾨니그 정리

이분 그래프에서 다음이 성립한다.

$$ \text{최대 매칭} = \text{최소 정점 덮개} $$

최소 정점 덮개는 모든 간선을 적어도 한 끝점이 덮도록 고른 최소 정점 집합이다.
또한 보집합 성질로

$$ \text{최대 독립 집합} = |V| - \text{최대 매칭} $$

도 따라온다. 이 정리들 덕분에 "최소한의 감시 지점", "최대한 많이 고르되 충돌
없게" 같은 문제가 모두 이분 매칭으로 환원된다.

복잡도

각 왼쪽 정점마다 한 번씩 DFS로 증가 경로를 찾으면 \(O(VE)\)다. 더 빠른
호프크로프트-카프는 BFS로 여러 증가 경로를 한 단계에 동시에 처리해
\(O(E\sqrt V)\)를 달성한다.

플로우와의 관계

이분 매칭은 네트워크 플로우의 특수한 경우다. 소스를 모든 \(L\)에 용량 1로,
모든 \(R\)을 싱크에 용량 1로 잇고 그룹 사이 간선 용량을 1로 두면 최대 유량이
곧 최대 매칭이다. 그래서 디닉을 그대로 써도 되지만, 전용 증가법이 구현이
간단하고 충분히 빠른 경우가 많다.

헝가리안 증가법 구현

match[r]은 오른쪽 정점 \(r\)에 매칭된 왼쪽 정점, visited는 한 번의 DFS에서
중복 방문을 막는다.

#include <bits/stdc++.h>
using namespace std;

const int MAXL = 1001;
vector<int> g[MAXL];     // 왼쪽 정점 -> 인접한 오른쪽 정점들
int match_[MAXL];        // 오른쪽 r에 매칭된 왼쪽 정점 (-1: 없음)
bool visited[MAXL];

bool dfs(int u) {        // u: 왼쪽 정점
    for (int v : g[u]) {
        if (visited[v]) continue;
        visited[v] = true;
        // v가 비었거나, v의 짝을 다른 곳으로 옮길 수 있으면 매칭
        if (match_[v] == -1 || dfs(match_[v])) {
            match_[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    int n, m; scanf("%d %d", &n, &m);  // 왼쪽 n개, 오른쪽 m개
    // ... 간선 입력 ...
    memset(match_, -1, sizeof(match_));
    int result = 0;
    for (int u = 1; u <= n; u++) {
        memset(visited, false, sizeof(visited));  // 매 시도마다 초기화
        if (dfs(u)) result++;
    }
    printf("%d\n", result);   // 최대 매칭 크기
    return 0;
}

흔한 실수

• visited 초기화 위치 — 왼쪽 정점 하나를 시도할 때마다(각 for u 반복마다)
  visited를 리셋해야 한다. 전체에서 한 번만 초기화하면 틀린다.
• 재귀 방향 — dfs(match_[v])는 "\(v\)의 현재 짝을 다른 데로 밀어낼 수
  있나"를 재귀로 묻는다. 이 한 줄이 증가 경로의 핵심이다.
• 양쪽 인덱스 충돌 — 왼쪽·오른쪽 정점 번호 공간을 분리하거나, match_를
  오른쪽 기준으로만 두는 식으로 일관성을 유지하자.

최소 정점 덮개 복원 (쾨니그)

최대 매칭을 구한 뒤, 매칭 안 된 왼쪽 정점에서 교대 경로로 도달 가능한 정점을
표시한다. 그러면 (도달 못 한 왼쪽) ∪ (도달한 오른쪽) 이 최소 정점 덮개이고,
그 보집합이 최대 독립 집합이다.

응용 패턴

특히 DAG의 최소 경로 덮개는 각 정점을 (출발용, 도착용)으로 쪼개 이분
매칭한 뒤 \(V - \text{매칭}\)으로 구하는 고전 기법이다. 이분 매칭은 모델링만
익히면 폭넓게 쓰이며, 가중치가 붙으면 이후의 MCMF나 헝가리안 알고리즘으로
확장된다.