Bipartitie Matching

안경잡이개발자 : 네이버 블로그

참고 블로그

Network Flow를 이용해 할 수 있는 대표적인 알고리즘이다. 어떤 A집단이 B집단을 선택할 때 가장 많은 연결이 발생하도록 하는 알고리즘이다.

예를 들어 아래와 같은 연결 관계가 있을 때

이를 Network Flow구조로 바꿀 수 있다.

이렇게 Network Flow구조로 생각하면 위에서 말한 최대 연결가능 횟수는 Maximum Flow문제가 되어버린다. 따라서 Edmonds-karp같은 Maximum Flow알고리즘을 적용시킬 수 있다.

Edmonds-karp의 시간복잡도는 $O(V*E^2)$인데 DFS를 이용하여 이분매칭 한해서 더 빠르게 만들 수가 있다.

수행 과정

Parent와 visit을 저장할 배열이 필요하다.

1. 모든 시작 노드에서 부터 DFS를 돈다. 아래의 과정을 반복한다. 매 반복마다 Visit만 초기화하고 Parent는 유지한다. DFS는 Bool을 반환하는 함수이고 True이면 해당 노드가 연결가능, False면 연결 불가능이다. 따라서 True일때 Count를 올려준다.
   1. 현재 노드에서 갈 수 있는 노드를 본다. visit된 상태라면 넘어가고, visit이 안되었다면 visit하고 다음과정을 수행한다.
   • 방금 선택한 노드가 아무도 선택하지 않았을 때 (빈 노드, Parent가 존재하지 않음.)
     • 현재 노드를 선택한 노드의 Parent로 지정해준다.
       • 일단은 현재 노드가 이 노드로 갈것이라는 얘기이다. 나중에 다른 노드에게 양보할 수 있다.
     • True를 반환한다.
   • 방금 선택한 도착 노드가 다른 노드가 이미 선택했다면 (Parent가 존재) 그 Parent노드에 대해서 DFS를 돈다. (a 과정으로 돌아감).
     • 이는 이미 선점한 노드가 다른 노드를 선택하도록 양보할 수 있냐는 것을 물어보는 것이다.
     • 만약 True가 반환되었다면 먼저 선점한 노드가 다른 노드를 선택할 수 있는 상황이다. 즉, 양보가 가능한 상황이다.
       • 현재 노드를 선택한 노드의 parent로 지정해준다.
       • True를 반환한다.
     • 만약 False가 반환되었다면 해당 노드가 양보가 불가능한 상황이다. 이 경우 Network가 성립될 수 없으므로 False를 반환한다.

최대 연결 수는 cnt를 통해 확인할 수 있고, 노드의 연결은 parent를 보면 된다.

예제 : 백준 1298번 노트북의 주인을 찾아서

1298번: 노트북의 주인을 찾아서

전형적인 문제이다.

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long LL;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define MAX 101

int n, m;
int a, b;
vi net[MAX];

bool visit[MAX];
int parent[MAX];

int cnt;

bool dfs(int cur) {
    for (auto next : net[cur]) {
        if (visit[next]) continue;
        visit[next] = true;

        if (!parent[next] || dfs(parent[next])) {
            parent[next] = cur;
            return true;
        }
    }
    return false;
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        net[a].push_back(b);
    }

    for (int i = 1; i <= n; i++) {
        memset(visit, false, sizeof(visit));
        if (dfs(i)) cnt++;
    }

    cout << cnt << '\\n';
}

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

    solve();
}