Bipartite Matching

Bipartite Matching

이분 매칭은 두 그룹간의 각 원소들을 한 번씩만 써서 매칭시켜주는 알고리즘이다.

대개 매칭 수의 최대값을 구하라는 문제가 기본이다.

BOJ 2188 - 축사 배정 문제를 보자.

소 $N$ 마리를 축사 $M$ 에 한 축사에 최대 한마리씩 얼마나 많이 넣을 수 있을지를 구해야 한다. 전형적인 이분 매칭 문제이다.

보통 $O(VE)$ 알고리즘이 쓰이고, 더 빠른 알고리즘으론 Dinic 알고리즘처럼 Level Graph 를 구축해 더 빠른 시간에 돌리는 Hopcroft-Karp $O(E\sqrt V)$ 알고리즘이 있다.

알고리즘 $O(VE)$

알고리즘의 기반은 DFS이다. 집합 $A$와 $B$가 있고 각 원소들이 서로 다른 집합의 원소들과 매칭될 수 있는지 여부를 알 때, 다음과 같이 수행한다.

$A$ 에 있는 원소 $a$ 를 $B$에 있는 원소와 매칭시킬 수 있는지 판단한다고 하자.

$a$ 에서 이어져있는 $B$ 에 있는 원소들을 훑는다고 할때 $B$ 쪽의 원소 $b$ 가 아직 $A$ 에 있는 원소와 매칭이 안되었다면 그것과 매칭시키고 알고리즘을 종료한다.

만약 $b$ 가 $A$ 의 원소와 매칭되어있다면, 그 매칭된 원소 $a’$ 를 $b$ 가 아닌 다른 원소와 매칭시킬 수 있는지 재귀적으로 살펴본다.

만약 $a’$ 가 $b$ 가 아닌 다른 $b’$ 와 매칭에 성공한다면 이제 $b$ 는 $a$ 랑 매칭시켜줄 수 있다.

만약 모든 $b$ 에 대해 매칭이 실패한다면 $a$ 는 어떤 원소와도 매칭시킬 수 없다.

이걸 $A$ 의 모든 원소에 대해서 수행하고 한 원소 $a$ 당 DFS를 돌려야 하므로,

시간복잡도는 $O(VE)$ 이다. ($V$=정점의 개수, $E$=간선의 개수)

구현

struct bipartite {  
   int N, M;  
   vvi edges;  
   vi vis, A, B;  
   bipartite(int N, int M = -1) : N(N), M(~M ? M : N) {  
      edges.resize(N);  
      A.resize(N, -1), B.resize(M, -1), vis.resize(N);  
   }  
   void add_edge(int f, int t) { edges[f].pb(t); }  
   bool dfs(int a) {  
      vis[a] = 1;  
      for (int b: edges[a]) {  
         if (B[b] == -1 || !vis[B[b]] && dfs(B[b])) {  
            A[a] = b, B[b] = a;  
            return 1;  
         }  
      }  
      return 0;  
   }  
   int match() {  
      int ret = 0;  
      for (int i = 0; i < N; i++)  
         fill(all(vis), 0), ret += dfs(i);  
      return ret;  
   }  
};

구현은 간단하다. dfs 함수는 위에서 설명한 동작을 그대로 수행하며 $A$ 는 $a\to b$ 로 가는 $b$ 의 번호를 갖고 있고, $B$ 는 $b \to a$ 로 가는 $a$ 의 번호를 갖고있다.

한 번의 DFS마다 $\text{visited}$ 배열을 초기화 시켜줌에 유의한다.

연습 문제

BOJ 2188 - 축사 배정

BOJ 15271 - 친구 팰린드롬 2

기본 문제이지만, 홀수 정점들과 짝수 정점들에 대한 이분 그래프로 나눈 후 구해주자.