(라이님 블로그 대회 알고리즘 따라잡기 29)호프크로프트 카프 알고리즘(Hopcroft-Karp Algorithm)

오늘은 호프크로프트 카프 알고리즘을 배워보았다. 블로그 글도 잘 설명되어 있지만 좋은 유튜브 영상을 하나 봐서 그것도 소개하고자 한다. 자세한 설명은 라이님 블로그 - 호프크로프트 카프 알고리즘을 참고하면 된다!!

(자세한 설명에 늘 압도적 감사를 표합니더,,)

 

이 알고리즘의 시간복잡도는 $O(E\sqrt{V})$로 디닉 알고리즘의 특수한 경우라고 생각하면 된다. 또한 이분 매칭을 빨리 한다는 점에서 이분 매칭(Bipartite matching)과도 닮아 있는데, 디닉 알고리즘과 이분 매칭 코드를 섞어놓은 코드다.

 

아무래도 영문으로 된 자료가 많은 만큼 아래 유튜브에 나온 정의가 조금 더 직관적인거 같아 유튜브에 나오는 정의로 정리해본다.

Hopcroft-Karp Algorithm

Augment Path) 

- Starts at an unmatched vertex

- Ends at an unmatched vertex

- The edges in the path alternate between being in the matching and not in the matching

Algorihm

코드는 늘 그렇듯 라이님의 블로그에서 감사하게도 참고했다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 10000;
const int INF = 1000000000;

int N, M;  // N: 그룹 A의 정점 수, M: 그룹 B의 정점 수
int A[MAX], B[MAX], dist[MAX];
bool used[MAX];
vector<int> adj[MAX];

// 호프크로프트 카프 전용 bfs 함수: A그룹의 각 정점에 레벨을 매김
void bfs() {
    queue<int> Q;
    for (int i = 0; i < N; ++i) {
        if (!used[i]) {
            dist[i] = 0;
            Q.push(i);
        } else {
            dist[i] = INF;
        }
    }

    while (!Q.empty()) {
        int a = Q.front(); Q.pop();
        for (int b : adj[a]) {
            if (B[b] != -1 && dist[B[b]] == INF) {
                dist[B[b]] = dist[a] + 1;
                Q.push(B[b]);
            }
        }
    }
}

// 호프크로프트 카프 전용 dfs 함수: 새 매칭을 찾으면 true
bool dfs(int a) {
    for (int b : adj[a]) {
        if (B[b] == -1 || (dist[B[b]] == dist[a] + 1 && dfs(B[b]))) {
            used[a] = true;
            A[a] = b;
            B[b] = a;
            return true;
        }
    }
    return false;
}

int main() {
    while (scanf("%d", &N) > 0) {
        // 그래프 정보 입력받기
        for (int i = 0; i < N; ++i) {
            int job, J;
            scanf("%d: (%d)", &job, &J);
            for (int j = 0; j < J; ++j) {
                int server;
                scanf("%d", &server);
                adj[job].push_back(server - N);
            }
        }

        // 호프크로프트 카프 알고리즘
        int match = 0;
        fill(A, A + N, -1);
        fill(B, B + M, -1);

        while (true) {
            bfs();

            int flow = 0;
            for (int i = 0; i < N; ++i) {
                if (!used[i] && dfs(i)) {
                    flow++;
                }
            }

            if (flow == 0) break;
            match += flow;
        }

        // 결과 출력
        printf("%d\n", match);

        // 초기화
        fill(used, used + N, false);
        for (int i = 0; i < N; ++i) {
            adj[i].clear();
        }
    }
    return 0;
}