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. 최대유량 값은 두 숫자를 동시에 뺀 값의 최댓값이다. 최대유량으로 뺀 값을 제외한 나머지 값은 한개씩 빼주어야하며, 최종적으로 "모든 숫자의 합 - 최대유량"을 출력하면 곧 정답이다.
오늘의 교훈) 격자판에서 인접한 두 칸을 묶을 경우 이분그래프로 만들어 줄 수 있다.