11014) 컨닝 2 & hopcroft-karp 알고리즘

hopcroft-karp 알고리즘은 이분 그래프에서 최대 매칭을 찾는 그래프이다.

이분 그래프에서 최대 매칭은 minimum vertex cover와 같다는 것을 생각하라.

이를 통해 최대 독립 집합을 구할 수 있다.

hopcroft-karp 알고리즘은 특히 시간 복잡도에서 상당히 유리한 이점을 가지고 있다. 솔직히 정확히는 얼마나 빠른지 모르겠따 ㅋ

대충 아이디어는 다음과 같다:

최대 매칭을 찾기위한 augmenting path를 찾는다.

예를 들어

이분 그래프에서

A B C D E F

가 나 다 라 마

와 같은 vertex가 있다고 가정하자.

그 중 전에 찾은 매칭이 "A - 가" 가 있다고 치자.

근데 만약에 아직 찾지 않은 매칭으로 " 나 - A - 가 - B"와 같은 경로가 있다고 했을 때,

찾은 매칭을 나 - A 와 가 -B로 바꿔준다면? 매칭의 갯수가 늘어나게 된다.

이를 이용한다.

1) bfs는 이분 그래프에서 왼쪽 그룹에 있는 level을 정한다.

만약 왼쪽 그룹에 있는 vertex가 매칭 그룹에 포함되지 않았다면 level은 0으로 설정하고 나머지는 INF로 설정한다.

이후 bfs를 이용해 level이 0인 vertex (가)부터 탐색하는데, 이 vertex (가)와 연결된 오른쪽 그룹의 vertex f에 대해서 vertex f가 이미 다른 왼쪽 그룹에 vertex (나)와 연결되어 있다면 해당하는 vertex (나)의 level을 업그레이드 해준다.

이렇게 level을 매기게 되면

경로의 순서가 나타나지게 되는데

(가) - level 0,
(나) - level 1이 된다.

이를 이용하여 dfs를 돌리게 된다.

2) dfs는 본격적으로 경로를 찾게된다.

이 경로는 항상 왼쪽 그룹의 level이 increment하는 방향으로 정해져야하며, 매칭 그룹에 있는 매칭들이 서로 바뀌게 된다.

이 때 이미 방문했던 정점에서 경로를 찾을 수 있는지 없는지를 컷팅하여 시간복잡도를 대폭 감소시킬 수 있다.

코드는 아래와 같다. 자세히 쓰기 귀찮다 ㅎㅇ

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

int C, N, M;
char map[81][81];

int A[6401], B[6401];
int lv[6401];

bool pos[6401];
vector<int> adj[6401];

int dx[6] = {-1, 0, 1, -1, 0, 1};
int dy[6] = {-1, -1, -1, 1, 1, 1};

void bfs(){
 queue<int> q;
 for(int i=0; i<6400; i++) {
  if(A[i]==-1) {
   lv[i] = 0;
   q.push(i);
  }
  else{
   lv[i] = -5;
  } 
 }
 
 while(!q.empty()){
  int idx = q.front(); q.pop();
  for(auto f : adj[idx]){
   if(B[f] != -1 && lv[B[f]] == -5){
    lv[B[f]] = lv[idx] + 1;
    q.push(B[f]);
   }
  }
 }
 
}

bool dfs(int n){
 if(!pos[n]) return 0;
 for(auto b: adj[n]){
  if(B[b] == -1) {
   A[n] = b;
   B[b] = n;
   return 1;
  }
  if(lv[B[b]] == lv[n] + 1){
   if(dfs(B[b])){
    A[n] = b;
    B[b] = n;
    return 1;
   }
  }
 }
 return pos[n] = 0;
}

int main(){
 scanf("%d", &C);
 while(C--){
  scanf("%d%d", &N, &M);
  for(int i=0; i<N; i++) scanf("%s", map[i]);
  int people = 0;
  
  for(int i=0; i<N; i++) {
   for(int j=0; j<M; j++){
    if(map[i][j] == '.') people++;
   }
  }
  
  for(int i=0; i<=6400; i++){
   A[i] = -1;
   B[i] = -1;
   adj[i].clear();
  }
  
  for(int i=0; i<N; i++) {
   for(int j=0; j<M; j+=2){
    for(int k=0; k<6; k++) {
     if( i+dx[k] < 0 || i+dx[k] >= N) continue;
     if( j+dy[k] < 0 || j+dy[k] >= M) continue;
     if( map[i][j] != '.') continue;
     if( map[i+dx[k]][j+dy[k]] == '.')
      adj[i*M + j].push_back( (i+dx[k]) * M + j+dy[k]);
     
    }
   }
  }
  
  int match = 0;
  while(1){
   int flow = 0;
   bfs();
   for(int i=0; i<=6400; i++) pos[i] = 1;
   for(int i=0; i<=6400; i++) if(A[i]==-1 && dfs(i)) flow++;
   
   if(!flow) break;
   match += flow;
  }
  
  printf("%d\n", people - match);
 }
}