1867 - 돌멩이 제거

문제 링크

---

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

문제 요약

---

\(N*N\)격자판위에 돌맹이들이 놓여져 있다. 한번의 작업으로 한개의 행이나 한개의 열에 있는 돌멩이를 모두 제거할 수 있다. 이 때 최소 몇번의 작업을 해야 격자판 위에 있는 돌멩이를 모두 제거할 수 있는지 구하는 문제다.

문제 풀이

---

처음 이 문제를 본다면 \(greedy\)로 접근을 하기 쉽다. 하지만 그렇게 접근을 시작하는 순간 문제는 미궁으로 빠지게 된다. 그렇다면 어떻게 접근을 해야할까? 우선 아래와 같은 격자판이 있다고 가정을 해보자.

위 격자판을 그래프로 생각해보자. 정점은 각각의 열과 행이고 돌멩이가 있는 칸은 열과 행을 잇는 간선이라고 생각을 한다. 그렇다면 그래프는 아래와 같이 그려진다.

만약에 \(R3\)에서 작업을 진행한다면 위 그래프에서는 어떻게 표시가 될까? 이를 다시 표현하면 아래와 같다.

자 이 그림을 본다면 이제 감이 와야 한다. 이 문제는 결국 행과 열, 그리고 돌맹이가 놓여진 칸들을 가지고 그래프로 모델링을 한 다음 \(Minimum\ vertex\ cover\)를 찾는 문제와 동치가 됐다. 일반적인 그래프에서 \(Minimum\ vertex\ cover\)를 구하는 문제는 \(NP-Complete\)으로 알려져 있다. 하지만 우리는 König's theorem에 의해서 이분 그래프에서의 최소 정점 덮개는 최대 매칭과 동치라는 것을 알 수 있다. (자세한 증명은 위키를 참고하면 좋겠다.)

※ \(Vertex\ cover\) 란 정점을 선택했을 때 선택한 정점에 인접한 모든 간선들이 커버가 된다고 했을 때 임의의 정점들을 선택 해 모든 간선들을 커버할 수 있는 집합을 의미한다. \(Minimum\ vertex\ cover\)는 \(Vertex\ cover\) 가 되는 집합들 중 집합의 크기가 가장 작은 집합을 의미한다.

이 문제는 행과 열로 이루어진 이분 그래프이고, 이분 그래프 내에서 최소 정점 덮개의 수를 구하는 문제이므로 최대 매칭을 구하는 문제로 변환해 풀 수 있게 된다.

소스 코드

---

#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

int n, m, u, v, V[510], bMatch[510];
vector<vector<int>> node;

int dfs(int here) {
  if (V[here]) {
    return 0;
  }
  
  V[here] = 1;
  for (int there : node[here]) {
    if (!bMatch[there] || dfs(bMatch[there])) {
      bMatch[there] = here;
      return 1;
    }
  }
  
  return 0;
}

int main() {
  scanf("%d%d", &n, &m);
  node.resize(n + 1);
  while (m--) {
    scanf("%d%d", &u, &v);
    node[u].push_back(v);
  }
  
  int ans = 0;
  for (int i = 1 ; i <= n ; ++i) {
    memset(V, 0, sizeof(V));
    if (dfs(i)) {
      ++ans;
    }
  }
  
  printf("%d\n", ans);
}