BOJ 3683 고양이와 개

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

고양이와 개가 나오는 티비쇼가 있고 사람들이 투표를 한다.

투표가 반영이 되면 시청자로 남고 반영이 안되면 시청을 그만둔다. 쇼 제작자는 시청자를 최대로 유지하고 싶다. 

 

문제를 다른 시각으로 보기

사람들 (혹은 플레이어, 참여자) 사이에 의견이 있다. 두 사람 사이의 의견에 충돌이 있으면, 두 사람도 만족을 하는 결과는 없다. 최소한 둘 중 하나는 결과에 불만족 하게 된다. (둘 다 될 수도 있다.)

이 문제를 그래프로 모델링 하기 위해 사람을 그래프를 구성하는 정점으로 볼 수 있다. 두 사람 사이의 의견 충돌이 있으면, 두 사람 사이에 간선을 추가 해서 의견 충돌을 모델링 할 수 있다. 그럼 이 문제는 서로 의견이 대립되지 않는 사람의 수를 최대화 하는 문제로 치환된다. 즉 그래프에서 최대 독립 집합(maximal independent set)을 구하는 문제로 볼 수 있다.

주어진 문제에서 사람들을 두 그룹으로 나눌 수 있다. 고양이파와 개파. 고양이파 끼리는 의견충돌이 없고, 개파끼리도 의견 충돌이 없다. 따라서 위에서 모델링한 그래프는 이분 그래프이다.

이분 그래프 G에서 최대 독립집합 I(G)는, 간선의 수 - 최대매칭과 일치한다.

엄밀히 말하면. 어떠한 그래프에서 |V| = I(G) + C(G) (C(G) vertex cover) 이다. 그리고 그래프가 이분 그래프인 경우 C(G) = M(G) (M(G) 최대 매칭) 이므로, |V| = I(G) + M(G) 이고, 따라서 I(G) = |V| - M(G) 이다.

오늘의 교훈:

• 사람들 사이의 의견 충돌을 그래프로 모델링 할 수 있다.
• 의견 충돌이 없는 사람들의 집합을 구하는 것은, 모델링한 그래프의 최대 독립집합을 구하는 것과 같다.
• 그래프가 이분매칭이라면, 최대 매칭을 구해서 문제를 해결할 수 있다.