[백준 11495번] 격자 0 만들기 (Python3)

from collections import *

def BFS():
  parent = [K]*K
  dq = deque([-1])
  while dq:
    now = dq.popleft()
    for next in adj[now]:
      if parent[next]==K and graph[now][next]-flow[now][next]:
        parent[next] = now
        dq.append(next)
        if next==-2:
          return parent

def solve():
  F = 0
  while parent:=BFS():
    now = -2; f = 1000
    while now+1:
      last = parent[now]
      f = min(f,graph[last][now]-flow[last][now])
      now = last
    now = -2
    while now+1:
      last = parent[now]
      flow[last][now] += f; flow[now][last] -= f
      now = last
    F += f
  return F  

for _ in range(int(input())):
  N,M = map(int,input().split()); K = N*M+2
  board = [[*map(int,input().split())] for i in range(N)]
  graph,flow = [[[0]*K for i in range(K)] for i in range(2)]
  adj = [[] for i in range(K)]
  for y in range(N):
    for x in range(M):
      i = y*M+x
      if (y+x)%2:
        graph[-1][i] = board[y][x]
        adj[-1].append(i); adj[i].append(-1)
        for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
          if N>(y1:=y+dy)>=0 and M>(x1:=x+dx)>=0:
            j = y1*M+x1
            graph[i][j] = 1000
            adj[i].append(j); adj[j].append(i)
      else:
        graph[i][-2] = board[y][x]
        adj[-2].append(i); adj[i].append(-2)
  print(sum(map(sum,board))-solve())

최대유량으로 해결하였다.

격자판(체스판)을 흰색칸과 검은색 칸으로 나누어 이분그래프를 만들어줄 수 있다는 점을 이용한다. 도미노 [백준 1824번] 도미노 (Python3) (tistory.com) 문제에서 이런 경험이 한번 있었기에 쉽게 눈치챌 수 있었지만 관련 문제를 풀지 않았다면 꽤나 어려운 문제일 것이다.

 

풀이를 설명하면,

1. y행 x열 칸에서 y+x가 홀수인 경우를 검은색 칸, 반대를 흰색칸이라고 둔다.

2. source-검은색칸-흰색칸-sink로 이어지는 그래프를 만든다. 이때 source-검은칸과 흰색칸-sink의 용량은 각 칸의 숫자와 같고, 검은색칸-흰색칸의 용량은 무제한으로 둬도 무방하다.

3. 2의 그래프를 토대로 최대유량을 찾는다.

4. 최대유량 값은 두 숫자를 동시에 뺀 값의 최댓값이다. 최대유량으로 뺀 값을 제외한 나머지 값은 한개씩 빼주어야하며, 최종적으로 "모든 숫자의 합 - 최대유량"을 출력하면 곧 정답이다.

 

 

오늘의 교훈) 격자판에서 인접한 두 칸을 묶을 경우 이분그래프로 만들어 줄 수 있다.