(라이님 블로그 대회 알고리즘 따라잡기 26) 이분매칭(Bipartite Matching)

오늘은 네트워크 플로우의 특수한 케이스인 이분 매칭에 대해 배워보았다. 이론은 상당히 단순한데, 내용은 라이님 블로그에 자세히 설명되어 있다.

 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220807541506&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

이분 매칭(Bipartite Matching)

 

라이님이 알려준 코드를 살짝만 수정해서 사용하고자 한다.

#include <iostream>
#include <vector>
#include <cstring> // memset 사용을 위해 포함
using namespace std;

const int MAX = 200;

// N: A 그룹 크기, M: B 그룹 크기
// A[i], B[i]: 각 정점이 매칭된 반대편 정점 번호
int N, M, A[MAX], B[MAX];
// adj[i]: A[i]와 인접한 그룹 B의 정점들
vector<int> adj[MAX];

// A그룹에 속한 정점 a를 이분 매칭시켜서 성공하면 true
bool dfs(int a, vector<bool>& visited){
    visited[a] = true;
    for(int b : adj[a]){
        // 반대편이 매칭되지 않았거나
        // 매칭되어 있었지만 원래 매칭되어 있던 정점을 다른 정점과 매칭시킬 수 있으면 성공
        // B[b] == -1이 참인 경우 뒤에 조건식은 확인하지 않음
        if(B[b] == -1 || (!visited[B[b]] && dfs(B[b], visited))){
            A[a] = b;
            B[b] = a;
            return true;
        }
    }
    // 매칭 실패
    return false;
}

int main(){
    ios::sync_with_stdio(false); // 빠른 입출력을 위해
    cin.tie(nullptr); // cin과 cout의 묶음을 풀어줌

    cin >> N >> M;
    for(int i = 0; i < N; i++){
        int S;
        cin >> S;
        for(int j = 0; j < S; j++){
            int k;
            cin >> k;
            adj[i].push_back(k - 1);
        }
    }

    int match = 0;
    // 초기값: -1
    memset(A, -1, sizeof(A));
    memset(B, -1, sizeof(B));
    int MAX_V = M > N ? M : N;
    for(int i = 0; i < N; i++){
        // 아직 매칭되지 않은 그룹 A 정점에 대해 매칭 시도
        if(A[i] == -1){
            vector<bool> visited(MAX_V, false);
            if(dfs(i, visited)) match++;
        }
    }
    cout << match << '\n';
}

 

 

이분 매칭(Bipartite Matching)을 이용해서 풀 수 있는 문제들 역시 라이님 블로그에 잘 소개되어 있다.

> 2188번 축사 배정 https://www.acmicpc.net/problem/2188