[백준] 11682 Landscaping Python 3

import sys
from collections import deque

class MaxFlow:
    def __init__(self, n):
        self.n = n
        # adj[u] = [ [v, rev_idx, capacity], ... ]
        #   - v: 다음 노드
        #   - rev_idx: v의 인접 리스트에서 이 간선의 역방향 간선 인덱스
        #   - capacity: 이 간선이 현재 흘려보낼 수 있는 잔여 용량
        self.adj = [[] for _ in range(n)]
        # 경로 복원을 위한 배열(역방향 간선의 인덱스를 저장)
        self.par = [-1] * n

    def add_edge(self, a, b, cap, rcap=0):
        """
        a -> b 용량이 cap인 간선과
        b -> a 용량이 rcap인 간선을 동시에 추가
        """
        # a->b 간선: (목적지 b, b의 역방향 리스트 인덱스, 용량 cap)
        self.adj[a].append([b, len(self.adj[b]), cap])
        # b->a 간선(역방향): (목적지 a, a의 역방향 리스트 인덱스, 용량 rcap)
        self.adj[b].append([a, len(self.adj[a]) - 1, rcap])

    def bfs(self, s, t):
        """
        에드몬드-카프 방식을 위한 BFS.
        s에서 t로 가는 경로를 찾으며, 그 경로에서 흘릴 수 있는
        최대 흐름값(임시)을 반환. 경로가 없으면 0 반환.
        """
        for i in range(self.n):
            self.par[i] = -1

        INF = 1 << 30
        self.par[s] = INF  # s까지 오는데 사용할 수 있는 유량(무한대 가정)
        queue = deque([(s, INF)])

        while queue:
            cur, flow_val = queue.popleft()
            for nxt, rev_idx, capacity in self.adj[cur]:
                # 아직 방문 안했고, 용량 남아있다면
                if self.par[nxt] == -1 and capacity > 0:
                    self.par[nxt] = rev_idx
                    new_flow = min(flow_val, capacity)
                    if nxt == t:
                        return new_flow
                    queue.append((nxt, new_flow))
        return 0

    def flow(self, s, t):
        """
        s에서 t로의 최대 유량을 계산 (에드몬드-카프)
        """
        total_flow = 0
        while True:
            f = self.bfs(s, t)
            if f == 0:
                break
            total_flow += f

            # 찾은 경로로부터 역으로 올라가며 유량을 갱신
            cur = t
            while cur != s:
                # par[cur] = 현재 노드(cur)에 연결된 "역방향 간선"의 인덱스
                rev_idx = self.par[cur]
                # 역방향 간선(즉, cur -> prv)을 찾아서 용량 증가
                prv, prv_rev_idx, _ = self.adj[cur][rev_idx]
                
                # cur -> prv (역방향 간선)의 잔여 용량 f만큼 증가
                self.adj[cur][rev_idx][2] += f
                # prv -> cur (정방향 간선)의 잔여 용량 f만큼 감소
                self.adj[prv][prv_rev_idx][2] -= f

                cur = prv
        return total_flow

def solve():
    input = sys.stdin.readline
    n, m, a, b = map(int, input().split())
    board = [input().rstrip() for _ in range(n)]

    s = n * m
    t = n * m + 1
    mf = MaxFlow(n * m + 2)

    # 격자의 각 칸을 번호로 매핑: (i, j) -> i*m + j
    # 추가로 s, t를 별도의 번호로 사용
    for i in range(n):
        for j in range(m):
            idx = i * m + j
            if board[i][j] == '.':
                # '.'인 칸은 s -> idx 로 용량 b
                mf.add_edge(s, idx, b)
            else:
                # '#'인 칸은 idx -> t 로 용량 b
                mf.add_edge(idx, t, b)

            # 상하/좌우 인접 연결 (가중치는 a)
            if i > 0:
                mf.add_edge((i - 1) * m + j, idx, a, a)
            if j > 0:
                mf.add_edge(i * m + j - 1, idx, a, a)

    print(mf.flow(s, t))

if __name__ == '__main__':
    solve()