1014. 컨닝

백준을 처음 풀었을 때부터 자주 보던 문제이다. 볼 때마다 음~ 어렵군 하고 넘겼던 기억이 있는데, 데일리 스터디에서 풀 문제로 선정되는 바람에......

 

어차피 모르는 문제이므로 스스로 푸는 건 깔끔하게^^ 포기했고, 그래프 공부하는 겸 글을 작성해 본다.

1014번: 컨닝

---

최대 이분 매칭 (Maximum Bipartite Matching)

이분 그래프에서 서로 다른 집합에 속하는 정점을 연결하는 간선을 이분 매칭이라고 한다. 한번 매칭에 사용한 정점을 다시 사용하지 않으면서 최대한 많은 매칭을 만드는 알고리즘을 최대 이분 매칭이라고 한다.

 

두 정점 간의 쌍을 최대한 많이 만드는 알고리즘이다. 예전에 경험치 많이 먹었던 알고리즘인데.. ㅎㅎㅎ

최대 독립 집합 (Maximum Independent Set)

그래프 $G$에 속하는 정점의 집합 $S$가 있다. $S$의 모든 정점이 서로 연결되어 있지 않다면 $S$는 독립 집합이다. 다른(any) 독립 집합의 부분집합이 아닌 독립 집합을 최대 독립 집합이라고 한다. 

 

간단하게 정점이 제일 많은 독립 집합이라고 생각해도 되....나?

최소 정점 커버 (Minimum Vertex Cover)

그래프 $G$에 속하는 정점의 집합을 $S$라고 하자. $G$의 모든 간선에 대해, 각 간선의 양 끝 정점 중 적어도 하나가 $S$에 속한다면 $S$를 정점 커버(Vertex Cover)라고 한다. $G$의 모든 정점 커버 중 정점의 수가 가장 적은 집합을 최소 정점 커버라고 한다.

 

중요! 최소 정점 커버의 여집합은 최대 독립 집합이다.

쾨닉의 정리

이분 그래프에서 최대 이분 매칭의 수는 최소 정점 커버에 속하는 정점의 수와 같다.

이분 매칭의 시간 복잡도가 $O(NM)$이므로($N$과 $M$은 각 정점 집합에 속하는 정점의 수) 이분 그래프에서는 최소 정점 커버를 다항 시간에 구할 수 있다.

 

그런데 이분 그래프가 아닌 그래프에서는 최소 정점 커버가 NP-Complete 문제라서 다항 시간에 구할 수 없다고 한다. 무려 NP-Complete라고..

그래서요?

사실 문제에서 주어진 교실은 이분 그래프이다. 열(column)을 하나의 집합으로 보면 된다. 따라서 책상을 정점으로, 컨닝할 수 있는 방향을 간선으로 삼는 이분 그래프를 그릴 수 있다.

 

앉힐 수 있는 사람의 수가 최대라는 말은 컨닝할 수 없는 사람의 수가 최대라는 것이다. 간선으로 연결된 두 정점은 컨닝할 수 있는 자리 pair이므로, 서로 연결되지 않은 정점을 최대한 많이 골라야 한다. 따라서 이 문제를 이분 그래프에서 최대 독립 집합에 속하는 정점의 수를 구하는 문제로 바꿀 수 있다.

 

최대 독립 집합에 속하는 정점의 수는 최소 정점 커버의 여집합의 크기와 같고, 최소 정점 커버의 크기는 최대 이분 매칭의 수와 같으므로 구하는 정답은 전체 정점의 수에서 최대 이분 매칭의 수를 뺀 값이다.

최종 정리

컨닝할 수 있는 두 책상(정점)을 연결하고, 최대 매칭의 수를 구해 전체 책상의 수에서 빼면 된다. 부서진 자리는 애초에 고려하지 않아야 한다.

 

아휴~ 힘들다.. 이제 구현만 잘 하자.

---

그와중에 오타 ㅋㅋㅋㅋㅋㅋㅋㅋ 미치겠다 진짜

참고

[알고리즘] Minimum Vertex Cover (최소 버텍스 커버) (2020-08-08 수정)

 

19. 최대 이분 매칭(Maximun Bipartite Matching)