BOJ 16056 - Plug It In

문제 링크 : https://www.acmicpc.net/problem/16056

문제 풀이

문제에서 주어진 정보를 그래프처럼 생각하면 정점을 가구와 콘센트 두 종류로 분류할 수 있다. 그리고 모든 간선은 가구와 콘센트 사이만을 잇는다. 즉, 이분그래프가 나오게 된다는 것이다. 그리고 최대 매칭값을 비슷하게 구하는 문제이기 때문에 이분 매칭을 떠올릴 수 있다.

이 문제의 가장 큰 특징은 하나의 콘센트에만 멀티탭을 꽃아서 3개의 가구와 연결을 시킬 수 있다는 것이다. 

생각을 해보자. 한번 이분매칭 했을 때 추가로 이을 가구가 존재하지 않는다면 그대로 답이 될 것이며, 연결이 되지 않은 두 개의 가구가 같은 콘센트에 매칭이 될 수 있으면 그 콘센트에 플러그를 꽃아 2개의 추가매칭을 만들 수 있다. 그렇지 않다면 1개의 추가 매칭을 만들 수 있다.

다르게 생각해보자. 어떠한 콘센트가 존재해서 그 콘센트에서 추가로 두개의 매칭을 할 수 있으면 답에 2를 더할 수 있다. 이분매칭을 할 때 정점을 순회하면서 매칭을 하나씩 추가시키는데, 모든 정점이 아니라 하나의 정점을 두번 추가로 생각해서 매칭을 두번 추가 시킬 수 있는지 각 정점에 대해서 보면 된다. 

구현 과정에서 맨 처음 전체 이분 매칭을 한 전체 상태를 저장하고 있다가 그 상태에 대해서 추가 매칭을 할 수 있는지 확인해야한다. 시간 복잡도는 $O(VE)$.