[C++ 알고리즘] 이분 매칭 (Bipartite Matching) (BOJ 2188번 : 축사 매칭)

이 포스트에서는 프로그래밍 알고리즘의 일종인 이분 매칭(Bipartite Matching)의 원리와 설명을 다룹니다.

또한 알고리즘의 적용을 효과적으로 설명하기 위해 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 2188번 : '축사 배정' 문제의 풀이 코드와 해설을 함께 다룹니다.

 

이분 매칭 알고리즘이란, 두 그룹 사이의 최대한 많은 일대일 대응을 구하는 알고리즘입니다.

이전에 다루었던 최대 유량 = 네트워크 플로우(Network Flow) 알고리즘의 특수한 상황을 다루는 알고리즘으로, 그래프의 노드를 두 그룹으로 나누어 연결을 지어야 하고 사이의 간선 용량이 모두 1인 상황에서만 적용이 가능합니다.

사용할 수 있는 조건이 더 강해진다는 단점이 있지만, 대신 조건만 맞는다면 O(VE^2)의 시간복잡도를 가졌던 기존의 네트워크 플로우 알고리즘보다 훨씬 빠른 O(VE) 시간에 알고리즘을 작동시킬 수 있습니다.

 

 

 

기본적인 이분 매칭 알고리즘의 작동 원리는 다음과 같습니다.

매칭을 시키는 기본 탐색 원리는 DFS이며, 왼쪽 그룹의 i번째 원소는 항상 오른쪽 그룹의 첫 번째 원소부터 매칭을 시도합니다.

만약 이미 매칭이 되어있다면 i-1번째 원소의 매칭 번호를 다음 번호로 늘리는 방식으로 회귀하면서 다음 매칭을 연결시켜서 i번째 원소가 매칭을 시킬 수 있도록 자리를 만들어줍니다.

이러한 방식으로 N번째 원소까지 모두 탐색을 완료했을 때 나오는 매칭이 최대 매칭이 됩니다.

 

그럼 이제 위의 아이디어를 코드로 어떻게 구현할 수 있는지 알아보기 위해, 적절한 예제를 하나 풀이해보도록 하겠습니다.

풀이할 문제는 백준 Online Judge의 2188번 : '축사 매칭' 문제입니다.

 

 

2188번 : 축사 매칭

2188번: 축사 배정

 

이 문제는 위의 이분 매칭의 조건을 문제로 그대로 옮겨놓은 문제입니다.

N마리의 소가 M개의 축사 중에서 들어가기를 원하는 일부 축사의 번호만 입력될 때, 축사에 배정시킬 수 있는 소들의 최대 마리 수를 구하는 문제입니다.

 

 

#include <bits/stdc++.h>
using namespace std;
const int MAX = 205;

int cow[MAX], shed[MAX];
vector<int> adj[MAX];
bool visited[MAX];

bool dfs(int from) {
    visited[from] = true;
    for(int i=0; i<adj[from].size(); i++) {
        int to = adj[from][i];
        if(shed[to] == -1 || (!visited[shed[to]] && dfs(shed[to]))) {
            cow[from] = to, shed[to] = from;
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;
    for(int from=1; from<=N; from++) {
        int S; cin >> S;
        while(S--) {
            int to; cin >> to;
            adj[from].push_back(to);
        }
    }

    int match = 0;
    fill(&cow[1], &cow[N+1], -1), fill(&shed[1], &shed[M+1], -1);
    for(int i=1; i<=N; i++)
        if(cow[i] == -1) {
            fill(&visited[1], &visited[N+1], false);
            if(dfs(i)) match++;
        }
    cout << match;
}

 

먼저 이분 매칭 문제에서는 노드의 그룹이 2개뿐이기 때문에 해당 그룹과 관련된 배열 2개를 선언하여, cow 배열에는 연결된 shed의 번호를 저장하고 shed 배열에는 연결된 cow 번호를 저장하도록 합니다.

이제 1번 cow부터 시작해서 N번 cow까지 각각 dfs를 수행해줄 것인데 그 전에 먼저 visited 배열을 -1로 초기화해줍니다.

 

i번 cow에 대해서 dfs를 수행할 때 i번 cow와 연결되어있는 shed들을 탐색하면서 만약 그 shed가 비어있다면 바로 배정을 해주고, shed가 이미 다른 cow와 연결이 되어있어도 그 shed와 연결된 cow가 다른 shed를 찾을 수 있도록 dfs를 재귀적으로 수행해줍니다.

그러면 그 cow는 visit하지 않은 다른 shed들 중에 배정이 될 수 있는 것으로 옮겨서 배정을 받고, 새로 배정시키려는 cow는 원래 들어가려고 했던 shed로 들어갈 수 있게 됩니다.

만약 모든 cow를 움직이려고 해도 더 이상 옮길 수 있는 방법이 없으면 false를 반환하여 탐색을 종료합니다.

 

최대 유량 알고리즘에 비해 간략화 된 알고리즘인만큼 코드 역시 비교적 짧음을 확연히 느낄 수 있습니다.

 

 

 

제출해보면 위와 같은 기록으로 정답 처리를 받아 통과할 수 있습니다.

 

이 문제에 한정해서는 이분 매칭을 적용시키기 쉽게 이분 매칭의 조건에 최적화되어 문제가 주어졌지만, 어려운 이분 매칭 문제들의 경우에는 문제 조건을 이분 매칭에 맞게 적용시키는 과정이 핵심으로 작용합니다.

다음 포스트부터는 다른 이분 매칭 문제들을 해결해보도록 하겠습니다.