이분 매칭(Bipartite Matching)

! 이분 그래프

• 그래프에 있는 정점들을 두 개의 독립적인 그룹으로 나눌 수 있고 같은 그룹 내에서는 서로 연결할 수 있는 간선이 없는 그래프를 의미한다.

A={1,2,3}
B={4,5,6}

위와 같은 그룹이 있을 때 이분 그래프는 다음과 같이 그릴 수 있다.

위처럼 정점 1,2,3의 그룹 사이에는 간선이 없고 정점 4,5,6의 그룹 사이에도 간선이 없다면 그룹 A, B에 대한 이분 그래프라고 할 수 있다.

• 이분 그래프에도 다음과 같은 특징이 있다.

1. 사이클의 길이가 홀수라면 이분 그래프가 아니다.
-예를 들어서 점이 3개 존재하고 서로 간선으로 연결되어서 사이클을 이룬다면 이분그래프를 이룰 수 없다.

2. DFS탐색 활용
-DFS탐색을 활용하여서 인접한 정점에 대해서 다른 색상을 칠할 수 있다면 이분그래프를 생성할 수 있다.

!이분 매칭

• 최대한 많은 간선을 찾아서 1:1로 정점을 연결하는 알고리즘이다.
• 단 정점을 연결할 때는 이미 정점이 연결되었다면 보통은 그 정점에 연결하지 않는다.

! 이분 매칭 코드 (BOJ 11375, 열혈강호)

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

int n, m;
vector<int> v[INF];
vector<int> A(INF, -1), B(INF, -1);
vector<int> visited;

bool dfs(int a) {
    visited[a] = true;
    for (auto b : v[a]) {
        if (B[b] == -1 || (!visited[B[b]] && dfs(B[b]))) {
            A[a] = b;
            B[b] = a;
            return true;
        }
    }
    return false;
}

int bipartite_matching() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        visited.assign(n + 1, false);
        if (dfs(i)) cnt += 1;
    }
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        for (int j = 0; j < x; j++) {
            int w;
            cin >> w;
            v[i].push_back(w);
        }
    }
    
    cout << bipartite_matching();
}

• 기본적으로 이분 매칭 알고리즘은 dfs를 보통 활용하여서 최대로 매칭을 해준다.
• 위의 문제에서는 한 사람에게 한 가지 일을 배분하여서 최대한 많은 작업을 해결하는 문제이다.

vector<int> v[INF];
vector<int> A(INF, -1), B(INF, -1);
vector<int> visited;
//v: 작업자가 할 수 있는 일 (간선)
//A, B: 작업자와 일을 연결해주는 배열
//visited: 작업자가 방문했다면 true

• 만약 1번 작업자가 2번 작업을 한다고 하면 A [1]=2, B [2]=1처럼 작성해 준다.

int bipartite_matching() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        visited.assign(n + 1, false);
        if (dfs(i)) cnt += 1;
    }
    return cnt;
}

• bipartate_matching에서는 1~n명의 작업자들이 돌아가면서 가능한 간선을 dfs를 통해서 확인해 준다.

bool dfs(int a) {
    visited[a] = true;
    for (auto b : v[a]) {
        if (B[b] == -1 || (!visited[B[b]] && dfs(B[b]))) {
            A[a] = b;
            B[b] = a;
            return true;
        }
    }
    return false;
}

visited: 작업자가 방문했다면 true

if (B[b] == -1 || (!visited[B[b]] && dfs(B[b]))) {
            A[a] = b;
            B[b] = a;
            return true;
}​

1. B[b] == -1
-정점 b가 아직 아무 정점과도 매칭되지 않았다면, 즉 빈자리라면 바로 a와 매칭시킨다.

2. (!visited[B[b]] && dfs(B[b]))
-만약 b가 이미 매칭된 상태라면, 기존에 매칭된 정점 B[b] 을 다른 곳으로 이동시킬 수 있는지 확인한다.
-visited[B[b]]를 확인하여 이미 방문한 정점이면 탐색을 중단한다.
-dfs(B[b])를 호출하여 B[b]에 매칭된 다른 정점을 이동시키고, b를 새로 매칭할 수 있는지 확인한다.
-만약 dfs(B[b])가 참이면, 기존 매칭을 변경할 수 있으므로 현재 a를 b와 매칭시킨다.

 

• 이분 매칭을 통해서 이분 그래프에서 1:1 매칭을 동시에 진행할 수 있다.