from collections import *
dy = [1,-1,0,0]; dx = [0,0,1,-1]
def BFS():
visited = [-1]*N*M*2; visited[K+N*M] = K
dq = deque([K+N*M])
while dq:
now = dq.popleft()
if now==H:
return visited
for next,c in graph[now]:
if visited[next]<0 and c-flow[now][next]:
visited[next] = now
dq.append(next)
def solve():
if (H,1) in graph[K+N*M]:
return -1
result = 0
while visited:=BFS():
now = H
result += 1
while now!=K:
last = visited[now]
flow[last][now] += 1; flow[now][last] -= 1
now = last
return result
N,M = map(int,input().split())
board = [input() for i in range(N)]
graph = [[(N*M+i,1)] for i in range(N*M)]+[[(i,0)] for i in range(N*M)]
for y in range(N):
for x in range(M):
if board[y][x]=="K":
K = y*M+x
if board[y][x]=="H":
H = y*M+x
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and M>x1>=0 and board[y1][x1]!="#":
graph[y1*M+x1+N*M].append((y*M+x,1))
graph[y*M+x].append((y1*M+x1+N*M,0))
flow = [{i:0 for i,c in graph[n]} for n in range(N*M*2)]
print(solve())최대유량 응용문제
이 문제는 K-H를 분리하는 문제로, 최소컷 문제로 볼 수 있다. 이때 최대유량-최소컷 정리에 따라 최소컷 = 최대유량임이 알려져있고, 따라서 최대유량 문제로 치환하여 해결할 수 있다.
이때 벽을 세우는데, 벽을 정점과 정점 사이에 세우는 것이 아니라 정점에 세우게 된다. 따라서 정점 그 자체를 하나의 간선으로 취급해야하며 이는 도시 왕복하기 2 https://rapun7el.tistory.com/372 문제와 유사한 문제임을 알 수 있다.
풀이를 설명하면,
1. 정점의 개수가 N*M개 이므로 그 2배인 크기 N*M*2의 인접그래프를 만든다.
2. y,x 좌표의 경우 i=y*M+x가 곧 자신의 번호이다. 이때 i와 i+N*M간에 용량 1의 간선을 만들고 역방향은 용량 0의 간선을 만든다. (도시왕복하기 2와 동일)
3. 벽(#)을 제외한 나머지 인접한 정점에 대해서 용량 1의 간선을 만들고 역방향은 용량 0의 간선을 만든다.
4. K와 H가 인접한 경우 -1을 출력하고, 그렇지 않은 경우 최대유량을 구하여 출력한다.
참고로 N*M*2가 최대 20000 이므로 graph나 flow를 n*n 인접행렬로 구성하면 메모리 초과가 발생하게 된다. 나는 그래프는 인접리스트를, flow는 dict를 이용하였다.
오늘의 교훈) 최소컷 문제는 최대유량 문제로 치환하여 해결할 수 있다.