[백준] 12670 The Year of Code Jam (Large) Python 3

import sys
from collections import deque

class Dinic:
    def __init__(self, n):
        """
        n: 전체 노드 수
        인접 리스트 구조:
        adj[u] = [(v, capacity, rev), ...]
          - v: 다음 노드
          - capacity: 잔여 용량
          - rev: v의 인접 리스트에서 역방향 간선의 index
        """
        self.n = n
        self.adj = [[] for _ in range(n)]
    
    def add_edge(self, u, v, cap, is_directed=True):
        """
        u -> v 용량 cap인 간선 추가.
        is_directed=False 이면 u <-> v 모두 용량 cap.
        """
        # 정방향 간선(u->v)
        self.adj[u].append([v, cap, len(self.adj[v])])
        # 역방향 간선(v->u)
        rev_cap = 0 if is_directed else cap
        self.adj[v].append([u, rev_cap, len(self.adj[u]) - 1])

    def bfs(self, s, t, level):
        """
        Dinic용 레벨 그래프 구성(BFS).
        level[u] = s에서 u까지의 최단거리(간선 수)
        t까지 도달하면 True, 아니면 False
        """
        for i in range(len(level)):
            level[i] = -1
        queue = deque()
        queue.append(s)
        level[s] = 0

        while queue:
            u = queue.popleft()
            for v, cap, _ in self.adj[u]:
                if cap > 0 and level[v] == -1:  # 잔여 용량 > 0, 방문 안 한 노드
                    level[v] = level[u] + 1
                    queue.append(v)
        return level[t] != -1

    def send_flow(self, u, flow, t, level, it):
        """
        Dinic용 DFS (Blocking Flow를 찾음).
          - u: 현재 노드
          - flow: 현재까지 흘릴 수 있는 유량
          - t: 싱크 노드
          - level: 레벨 그래프
          - it[u]: u에서 탐색을 시작할 간선 인덱스 (중복 탐색 방지)
        """
        if u == t:
            return flow

        while it[u] < len(self.adj[u]):
            v, cap, rev = self.adj[u][it[u]]
            if cap > 0 and level[v] == level[u] + 1:
                # 다음 노드로 보낼 수 있는 잔여 용량만큼 보내보기
                cur_flow = min(flow, cap)
                temp_flow = self.send_flow(v, cur_flow, t, level, it)

                if temp_flow > 0:
                    # 간선 용량 갱신
                    self.adj[u][it[u]][1] -= temp_flow  # 정방향 잔여 용량 감소
                    self.adj[v][rev][1] += temp_flow    # 역방향 잔여 용량 증가
                    return temp_flow
            it[u] += 1

        return 0

    def max_flow(self, s, t):
        """
        Dinic 알고리즘으로 s->t 최대 유량 계산
        """
        if s == t:
            return -1

        total = 0
        level = [-1] * self.n

        # 레벨 그래프가 더 이상 s에서 t로의 경로를 만들지 못할 때까지 반복
        while self.bfs(s, t, level):
            # it[u]: u에서 탐색해야 할 간선의 시작 인덱스 (중복 DFS 방지)
            it = [0] * self.n

            while True:
                flow = self.send_flow(s, float('inf'), t, level, it)
                if flow <= 0:
                    break
                total += flow

        return total


def solve_one_case(n, m, grid):
    """
    문제에서 주어진 로직대로 그래프 구성 후 Dinic으로 최대 유량 계산
    n, m: 그리드 크기
    grid: '.' / '#' / '?' 등이 섞인 2차원 문자 리스트
    """
    s = n * m
    t = n * m + 1
    mf = Dinic(n * m + 2)

    for i in range(n):
        for j in range(m):
            idx = i*m + j

            # (i>0) → (i-1, j) <-> (i, j)
            if i > 0:
                mf.add_edge(idx - m, idx, 1, is_directed=False)
            # (j>0) → (i, j-1) <-> (i, j)
            if j > 0:
                mf.add_edge(idx - 1, idx, 1, is_directed=False)

            if grid[i][j] == '?':
                continue

            # ('.') ^ ((i+j)&1) → s->node, 아니라면 node->t
            if ((grid[i][j] == '.') ^ ((i+j) & 1)):
                mf.add_edge(s, idx, 4)
            else:
                mf.add_edge(idx, t, 4)

    max_f = mf.max_flow(s, t)
    return 2*n*m - n - m - max_f


def main():
    input = sys.stdin.readline
    T = int(input().strip())
    for tc_num in range(1, T + 1):
        n, m = map(int, input().split())
        # C++ 코드에서 (n+2)x(m+2)에 '.'으로 패딩
        padded_grid = [['.' for _ in range(m + 2)] for _ in range(n + 2)]
        for i in range(n):
            row_str = input().rstrip()
            for j in range(m):
                padded_grid[i+1][j+1] = row_str[j]

        # 문제에서 n+2, m+2로 패딩된 그리드를 사용
        ans = solve_one_case(n + 2, m + 2, padded_grid)
        print(f"Case #{tc_num}: {ans}")

if __name__ == '__main__':
    main()