[BOJ 11014] 컨닝 2

문제

---

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

풀이

---

maximal independent set을 모르면 못 푸는 문제다.

그래프 G=(V, E)의 independent set의 정의는 다음과 같다.

\[I \subset E s,t \forall v, u \in I (v, e) \notin E\]

maximal이 붙으면 크기가 제일 큰 independent set을 의미한다.

동시에 앉으면 안 되는 자리끼리 엣지로 이어주면, 문제의 답은 maximal independent set의 크기가 된다.

여기서 포인트는 independent set의 complement가 vertex cover라는 점이다.

그러므로 maximal independent set의 complement는 minimal vertex cover가 되고, 돌멩이 제거에서 언급한 Kőnig’s Theorem을 이용하면 최대 매칭의 수로 답을 구할 수 있다.

코드

---

import sys


def dfs(cur):
    visit[cur] = 1
    for nxt in graph[cur]:
        if (b[nxt] == -1) or (not visit[b[nxt]] and dfs(b[nxt])):
            a[cur] = nxt
            b[nxt] = cur
            return 1
    return 0


for _ in range(int(sys.stdin.readline())):
    n, m = map(int, sys.stdin.readline().split())
    k = n * m
    ans = k
    board = []
    for __ in range(n):
        row = sys.stdin.readline().strip()
        ans -= row.count('x')
        board.append(row)
    
    graph = [[] for __ in range(k)]

    for j in range(1, m, 2):
        for i in range(n):
            if board[i][j] == '.':
                if board[i][j - 1] == '.':
                    graph[n * j + i].append(n * (j - 1) + i)
                
                if j < m - 1:
                    if board[i][j + 1] == '.':
                        graph[n * j + i].append(n * (j + 1) + i)
                    
                    if i and (board[i - 1][j + 1] == '.'):
                        graph[n * j + i].append(n * (j + 1) + i - 1)
                    
                    if (i < n - 1) and (board[i + 1][j + 1] == '.'):
                        graph[n * j + i].append(n * (j + 1) + i + 1)
                
                if i and (board[i - 1][j - 1] == '.'):
                    graph[n * j + i].append(n * (j - 1) + i - 1)
                
                if (i < n - 1) and (board[i + 1][j - 1] == '.'):
                    graph[n * j + i].append(n * (j - 1) + i + 1)

    a = [-1] * k
    b = [-1] * k
    for j in range(1, m, 2):
        for i in range(n):
            visit = [0] * k
            ans -= dfs(n * j + i)

    print(ans)