[Algorithm] 이분매칭(Bipartite Matching)

N명의 사람이 M개의 일을 해야하는데 각 일에는 한사람만 할당이 가능하다.

이때 최대한 일을 많이 처리하기 위해서 몇명의 사람을 할당할 수 있을까?

 

해당 문제를 풀기 위해서 완전 탐색등을 사용할 수 있다.

하지만 N과 M이 커질경우 해당 방식도 기하급수적으로 커진다.

 

그렇다면 이런 문제를 어떻게 풀어야할까??

 

여기서 나오는 것이 이분 매칭이다.

 

이분 그래프

인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프이며

그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결돼 있는 그래프를 의미한다.

 

 

이분 매칭

아래와 같이 A, B, C, D, E라는 사원이 있고 1, 2, 3, 4, 5라는 총 5개의 일이 있다고 가정해보자

 

이때 A라는 사원은 2번과 5번 일을 수행할 수 있고

B사원은 2, 3, 4
C사원은 1, 5

D사원은 1, 2, 5

E 사원은 2번 일을 할 수 있다.

 

이때 가장 많은 일을 하기 위해서 인원 배치를 어떻게 해야할까?

그리디하게 A 사원부터 살펴보면서 간선을 확인하며 이미 일이 점유된 경우 다음간선을 확인하며 할당해줘야 할까??

만약 그렇게 매칭했을경우 최대인것이 보장이 될까?

 

 

해당 그림을 보자 A사원은 3번 일에 매칭이 되었고 B사원는 1에 매칭이 되었다 이때 C사원은 3번밖에 갈 수 없는데 A 사원에 매칭되어있기에 최대 일을 할 수 있는 개수는 2개가된다.

 

하지만 A 사원이 1번일을 점유하면 C도 3번 일을 점유할 수 있기에 3개가 가능하다. 

 

이를 구하기 위해서 dfs(깊이 우선 탐색)을 사용하여 만약 C가 3을 점유할때 이미 점유가 되어 있으면 점유되어 있는 사원한테 물어보는것이다

 

"너 다른 일 점유할 수 있어?" 그렇다면 A 사원은 다른 일을 찾을테고 남은 일이 1이므로 1을 점유하고 C는 3을 점유하여 최대의 일을 찾을 수 있다.

 

 

코드 구현

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

struct Tree {
    int left, right;
};

const int INF = 1e9;
const int MAX = 100001;
const int D = 2000000;
const int MOD = 10007;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N, M;
vector<vector<int>> v(201);
int job[201];
bool check[201];
int result;

bool dfs(int node) {
    for(int i = 0; i < v[node].size(); i++) {
        int bar = v[node][i];

        if(check[bar]) continue;
        check[bar] = true;

        if(job[bar] == 0 || dfs(job[bar])) {
            job[bar] = node;
            return true;
        }
    }

    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N >> M;

    for(int i = 1; i <= N; i++) {
        int a;
        cin >> a;

        for(int j = 0; j < a; j++) {
            int b;
            cin >> b;
            v[i].push_back(b);
        }
    }

    for(int i = 1; i <= N; i++) {
        memset(check, 0, sizeof(check));
        if(dfs(i)) result++;
    }

    for(int i = 1; i <= N; i++) {
        if(job[i] != 0) {
            cout << job[i] << " -> " << i << endl;
        }
    }
}

 

자 핵심 부분만 살펴보자

 

vector<vector<int>> v(201);
int job[201];
bool check[201];
int result;

bool dfs(int node) {
    for(int i = 0; i < v[node].size(); i++) {
        int bar = v[node][i];

        if(check[bar]) continue;
        check[bar] = true;

        if(job[bar] == 0 || dfs(job[bar])) {
            job[bar] = node;
            return true;
        }
    }

    return false;
}

 

먼저 v 변수는 사원과 일에 대한 관계를 나타낸 것이다 A, B, C를 1, 2, 3 사원이라고 하고 일도 1, 2, 3으로 가정했을때 인접리스트에 대한 관계로 나타낼 수 있으며 job 배열은 일에 대한 소유권이 누구인지를 나타내는 배열이며

 

check 배열은 다른 일을 부탁할때 해당 일을 방문했는지 체크하는 배열이다 해당 배열이 없는 경우 계속 무한으로 재귀에 빠질 수 있기에 꼭 필요하다.

 

        if(job[bar] == 0 || dfs(job[bar])) {
            job[bar] = node;
            return true;
        }

해당 부분에서 job[bar] == 0인 경우는 일에 점유되지 않는 경우 또는 dfs(job[bar])을 하여 이미 소유된 일인 경우 다시 dfs 탐색을 해서 다른 일을 소유할 수 있는지 확인하는 부분이다.

 

만약 다른 일이 소유되지 않았을 경우 job 배열에 기록을 해주고 true를 리턴하여 성공했다고 알려주며 해당 사원에 대해 모든 일을 살펴봤을때 없는 경우 false를 리턴하여 실패했다고 알려준다.

 

첫번째 사진에 대한 답은 결국 아래 사진과 같이 나온다.

 

 

이분 매칭 알고리즘을 간단하게 공부할 수 있는 문제이다.

 

 

https://www.acmicpc.net/problem/2188

BOJ 서비스 종료

 

해당 알고리즘은 이번 문제와 마찬가지로 n명의 사람에게 m명의 일을 할당해야 하는 경우 또는 CS관점에서 N개의 프로세스에 M개의 메모리와 자원을 겹치지 않게 할당하는 경우 처럼 여러 관점에서 유용하게 쓰일 수 있다.