Algorithm in A..Z - Binary Matching (Hopcroft-Karp)

개념

이분 그래프가 있을 때 A집합과 B집합을 최대한 매칭하는 경우

 

Alternating Path(교차 경로)

그래프 위의 경로 중 매칭되지 않은 정점부터 시작하여 매칭을 이어주고 있지 않은 간선과 이어주는 간선이 교차하면서 반복되는 경로 (X - O - X - O - X ....) (X : 연결안된 정점, O : 연결된 정점)

 

Augmentine Path(증가 경로)

양 끝 정점이 매칭되어 있지 않은 교차경로

 

교차경로 안에서 증가경로를 반전하면 매칭의 크기를 늘릴 수 있다.

---

작동원리

1. A그룹에서 매칭에 속하지 않은 정점들의 레벨을 구한다.

2. 증가 경로를 체크한다.

3. 더 이상 증가경로를 찾지 못할 때까지 반복한다.

---

시간복잡도

O(V^(1/2) * E)

---

문제

9525 룩 배치하기

www.acmicpc.net/problem/9525

9525번: 룩 배치하기

---

코드

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

int N;
vector<vector<int>> graph;

vector<bool> isMatched;
vector<int> depth, isChecked;
void bfs() {
    queue<int> que;
    for (int i = 0;i < N;++i) {
        if (!isMatched[i]) {
            que.push(i);
            depth[i] = 0;
        } else {
            depth[i] = INT32_MAX;
        }
    }

    while (!que.empty()) {
        auto now = que.front();que.pop();

        for (auto &next : graph[now]) {
            if (isChecked[next] != -1 && depth[isChecked[next]] == INT32_MAX) {
                depth[isChecked[next]] = depth[now] + 1;
                que.push(isChecked[next]);
            }
        }
    }
}

bool dfs(int now) {
    for (auto &next : graph[now]) {
        if (isChecked[next] == -1 || (depth[now] + 1 == depth[isChecked[next]] && dfs(isChecked[next]))) {
            isChecked[next] = now;
            isMatched[now] = true;
            return true;
        }
    }

    return false;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n;
    cin >> n;

    vector<string> map(n);
    for (auto &str : map) {
        cin >> str;
    }

    int h = 0;
    vector<vector<int>> horizontal(n, vector<int>(n, -1));
    for (int y = 0;y < n;++y) {
        for (int x = 0;x < n;++x) {
            if (map[y][x] == '.') {
                while (x < n && map[y][x] == '.') {
                    horizontal[y][x] = h;
                    x++;
                }

                h++;
            }
        }
    }

    int v = 0;
    vector<vector<int>> vertical(n, vector<int>(n, -1));
    for (int x = 0;x < n;++x) {
        for (int y = 0;y < n;++y) {
            if (map[y][x] == '.') {
                while (y < n && map[y][x] == '.') {
                    vertical[y][x] = v;
                    y++;
                }

                v++;
            }
        }
    }

    N = h;
    graph.resize(N, vector<int>());
    for (int y = 0;y < n;++y) {
        for (int x = 0;x < n;++x) {
            if (map[y][x] == '.') {
                graph[horizontal[y][x]].emplace_back(vertical[y][x]);
            }
        }
    }

    depth.resize(h);
    isChecked.resize(v, -1);
    isMatched.resize(h, false);

    int ans = 0;
    while (true) {
        bfs();

        int flow = 0;
        for (int i = 0;i < h;++i) {
            if (!isMatched[i]) {
                flow += dfs(i);
            }
        }

        if (flow) {
            ans += flow;
        } else {
            break;
        }
    }

    cout << ans << "\n";
}