바둑 (Topcoder SRM 594, BOJ 9495)

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

혼자 못풀고 결국 풀이를 봤는데, 풀이가 상당히 멋져서 소개.

득점을 하는 방법을 쭉 따져보자.

1. 절대 'x'로 득점을 할 수 없다.

2. 'o'로 득점을 하려면 주위에 있는 '.' 들은 모두 차있어야 한다. 즉 주위에 있는 '_'에서 득점할 수 없다.

3. '_'로 득점을 하려면 주위에 있는 'o' 들은 모두 차있어야 한다. 즉 주위에 있는 'o' 에서 득점할 수 없다.

벌써 답이 나왔다. 인접한 'o' - '.' 쌍을 모두 이었을 때의 최대 독립 집합 정점 수 를 계산하면 이 문제를 풀 수 있다. degree가 0인 'o'는 없음이 문제 조건에 있으며, '.'는 그냥 넣어줘도 무방하다.

새롭게 생기는 그래프는 일단 격자 그래프의 subgraph인 데다가, 'o' - '.' 쌍을 이은 형태이기 때문에 자명히 이분 그래프이다.

이 때, 이분 그래프의 최대 독립 집합의 정점 수는 전체 정점 - (이분 매칭) 이다. 이를 출력하면 된다.