이분매칭 / Hopcroft-Karp Algorithm / 백준 11375 열혈강호 cpp

이분매칭(bipartite matching)은 정점들의 집합 간의 매칭을 계산하는 문제입니다. bipartite graph와 bipartite matching에 대한 설명은 아래 글을 참고하면 좋습니다.

https://gazelle-and-cs.tistory.com/12

쾨니그의 정리 (Kőnig's Theorem)

 

https://gazelle-and-cs.tistory.com/35

호프크로프트-카프 알고리즘 (Hopcroft-Karp Algorithm)

 

---

 

Hopcroft-Karp 알고리즘은 이분 그래프에서 최대 매칭 개수를 구하는 이분 매칭 문제를 푸는 알고리즘입니다.

복잡도는 O((V+E) sqrt(V)) 이며, 대략 O(V^2.5) 입니다. 

 

핵심적인 내용은 아래와 같습니다. 

nil : 매칭이 없는 가상의 정점. 탐색 종료 여부를 결정한다. 

증강 경로 : 현재 매칭에 포함되지 않은 간선을 통해 시작점에서 끝점까지 이동하며, 매칭 상태를 뒤집어 매칭 크기를 1 늘릴 수 있는 경로. 

bfs : 매칭이 없는 왼쪽 정점들을 시작점으로, 각 왼쪽 정점까지의 최소 거리 (레벨) 를 계산한다. 가능한 증강 경로들이 어떤 순서로 탐색되어야 하는지 결정. 

dfs : bfs로 계산한 레벨 정보를 이용해 실제 증강 경로를 따라가며 경로를 찾는다. 경로를 찾으면, 해당 경로 상의 매칭을 뒤집어 매칭의 크기를 늘린다. 

 

Hopcroft-Karp 알고리즘은 이분 매칭을 계산하기 위해 다음과 같이 동작합니다. 

1. 초기화 : 모든 정점의 매칭 상태를 초기화한다. (nil과 연결) 

2. bfs (레벨링) 

- 매칭이 없는 왼쪽 정점들을 큐에 넣고, 이들의 거리를 0으로 설정한다. (매칭이 있으면 inf, 큐에 안 넣음) 

- 큐에서 하나씩 정점을 꺼내 인접한 오른쪽 정점을 확인한다. 

- 해당 오른쪽 정점이 매칭되어 있다면, 매칭된 왼쪽 정점의 거리를 현재 탐색 중인 왼쪽 정점의 거리보다 1 큰 값으로 설정한다. 그리고 큐에 넣는다. 

- 위 과정을 반복해 nil까지 도달 가능한지 확인한다. nil까지 도달할 수 있다면 증강 경로가 존재함을 의미한다. 

3. dfs (증강 경로 탐색 및 매칭 업데이트) 

- bfs의 레벨 정보를 이용해 매칭이 없는 왼쪽 정점에서부터 dfs를 시작한다. 

- 레벨이 증가하는 방향으로 증강 경로를 찾는다. 

- 증강 경로를 찾으면, 해당 경로에 있는 매칭을 뒤집어 (기존 매칭 해제, 새로운 매칭 설정) 매칭의 전체 크기를 1 늘린다. 

- 더 이상 진행이 불가능한 경로라면, 해당 정점의 거리를 inf로 설정한다. (불필요한 추가 탐색 방지) 

 

---

 

위 내용을 이용해 이분 매칭 문제인 열혈강호 문제를 풀면 아래와 같습니다.

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

 

사람을 왼쪽 정점 집합, 일을 오른쪽 정점 집합으로 잡으면 이분 그래프에서 최대 매칭 개수를 구하라는 것과 동일합니다.

(열혈강호2는 최대 2개의 일을 할 수 있는 문제입니다. 이것은 복제본 사람을 모두 한 명 더 만들면 이분 매칭과 동일합니다.)

(https://www.acmicpc.net/problem/11376)

 

따라서 Hopcroft-Karp 알고리즘으로 위 문제를 풀면 아래와 같습니다. 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, M;
int INF = 987654321;

vector<vector<int>> edges; // 왼쪽 (사람) 기준, 연결된 오른쪽 (일)
vector<int> dist; // 왼쪽 정점 거리 (bfs용)
vector<int> matchL; // 왼쪽 정점과 매칭된 오른쪽 정점 (0 : nil)
vector<int> matchR; // 오른쪽 정점과 매칭된 왼쪽 정점 

void init() {
    cin >> N >> M;
    edges.resize(N + 1);
    dist.resize(N + 1);
    matchL.resize(N + 1);
    matchR.resize(M + 1);

    int work, num;
    for(int i = 1; i <= N; i++) {
        cin >> work;
        while(work--) {
            cin >> num;
            edges[i].push_back(num);
        }
    }
}

bool bfs() {
    // 증강 경로 레벨 설정 
    // nil (0) 까지 도달하는 경로 있으면 증강 경로 있는 거, 없으면 없는 거 
    queue<int> q;
    dist[0] = INF;

    for(int u = 1; u <= N; u++) {
        if(matchL[u] == 0) {
            // 아직 매칭 없는 왼쪽 정점
            dist[u] = 0;
            q.push(u);
        } else {
            dist[u] = INF;
        }
    }

    while(!q.empty()) {
        int u = q.front();
        q.pop();

        // 증강 거리 계산 
        // 오른쪽이 매칭되어 있으면, 매칭된 왼쪽 정점 거리를 현재 왼쪽 정점 거리보다 1 크게 설정 
        if(dist[u] < dist[0]) {
            for(auto v : edges[u]) {
                int matched = matchR[v];
                if(dist[matched] == INF) {
                    dist[matched] = dist[u] + 1;
                    q.push(matched);
                }
            }
        }
    }

    return dist[0] != INF;
}

bool dfs(int u) {
    // u에서 시작하는 증강 경로 찾음 
    if(u == 0) return true;

    for(auto v : edges[u]) {
        int matched = matchR[v];
        if(dist[matched] == (dist[u] + 1) && dfs(matched)) {
            // 증강 경로 있는 경우, 매칭 반전 
            matchL[u] = v;
            matchR[v] = u;
            return true;
        }
    }

    // 더 이상 증강 경로 없음 
    dist[u] = INF;
    return false;
}

int calc() {
    // 최대 매칭 개수 찾기 
    int result = 0;
    while(bfs()) {
        for(int u = 1; u <= N; u++) {
            if(matchL[u] == 0 && dfs(u)) result++;
        }
    }

    return result;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    init();
    cout << calc();
}