[BOJ 12961] 체스판 2

문제

---

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

풀이

---

flow network 구상이 전부인 문제이다.

L-모양 타일은 검정 칸, (홀수, 짝수)의 흰색 칸, (짝수, 홀수)의 흰색 칸을 정확히 하나씩 차지한다.

그러므로 세 개 층의 flow network를 만들어주면 된다.

검정 칸은 한 번만 덮일 수 있으므로, 정점 분할도 해줘야 한다.

코드

---

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
k = 2 * n * m + 2
board = [sys.stdin.readline().strip() for _ in range(n)]
graph = [[] for _ in range(k)]

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

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

ans = 0
while True:
    prev = [-1] * k
    queue = deque([k - 2])
    while queue:
        cur = queue.popleft()
        
        for nxt in graph[cur]:
            if nxt == k - 1:
                prev[nxt] = cur
                break
               
            if prev[nxt] == -1:
                prev[nxt] = cur
                queue.append(nxt)

        if prev[-1] != -1:
            break
    
    if prev[-1] == -1:
        break

    ans += 1
    nxt = k - 1
    while nxt != k - 2:
        cur = prev[nxt]
        graph[cur].remove(nxt)
        graph[nxt].append(cur)
        nxt = cur

print(ans)