티스토리 뷰

공부

바둑 (Topcoder SRM 594, BOJ 9495)

구사과 2015. 4. 26. 03:05

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


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


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

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

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

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


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

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

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


'공부' 카테고리의 다른 글

초고속철도 (KOI 2007)  (2) 2015.05.15
Palembang Bridges (APIO 2015)  (0) 2015.05.11
바둑 (Topcoder SRM 594, BOJ 9495)  (0) 2015.04.26
Mafia (BOI 2008)  (1) 2015.03.28
VK Cup 2015 — Round 1 (online mirror)  (0) 2015.03.22
K-th Number (NEERC 2004)  (3) 2015.03.15
댓글
댓글쓰기 폼
공지사항
Total
807,181
Today
375
Yesterday
1,251