[BOJ 1420] 학교 가지마!

문제

---

https://www.acmicpc.net/problem/1420

풀이

---

우선 현재 위치와 학교가 인접할 때만 학교에 가는 것을 막을 수 없다.

그렇지 않다면, 현재 위치를 source로 하고, 학교를 sink로 하며, 각 위치에 정점 분할 (in -> out)을 적용한 flow network를 구상한다.

이때 MFMC theorem을 이용하면, 최대 유량이 정답이 된다.

코드

---

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
board = [sys.stdin.readline().strip() for _ in range(n)]
graph = [[] for _ in range(2 * n * m)]

for i in range(n):
    for j in range(m):
        if board[i][j] == '#':
            continue

        if board[i][j] == 'K':
            x, y = i, j
            start = m * i + j + m * n
        
        elif board[i][j] == 'H':
            z, w = i, j
            end = m * i + j
            continue

        graph[m * i + j].append(m * i + j + m * n)
        
        if i and (board[i - 1][j] not in 'K#'):
            graph[m * i + j + m * n].append(m * (i - 1) + j)
        
        if (i < n - 1) and (board[i + 1][j] not in 'K#'):
            graph[m * i + j + m * n].append(m * (i + 1) + j)
        
        if j and (board[i][j - 1] not in 'K#'):
            graph[m * i + j + m * n].append(m * i + j - 1)
        
        if (j < m - 1) and (board[i][j + 1] not in 'K#'):
            graph[m * i + j + m * n].append(m * i + j + 1)

if abs(x - z) + abs(y - w) == 1:
    print(-1)
    exit()

ans = 0
while True:
    prev = [-1] * (2 * n * m)
    queue = deque([start])
    while queue:
        cur = queue.popleft()
        
        for nxt in graph[cur]:
            if nxt == end:
                prev[end] = cur
                break
            
            if prev[nxt] == -1:
                prev[nxt] = cur
                queue.append(nxt)

        if prev[end] != -1:
            break
    
    if prev[end] == -1:
        break

    ans += 1
    nxt = end
    while True:
        cur = prev[nxt]
        graph[cur].remove(nxt)
        graph[nxt].append(cur)
        nxt = cur
        if nxt == start:
            break

print(ans)