[BOJ 16407] Cops and Robbers

문제

---

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

풀이

---

학교 가지마!와 비슷하게 flow network를 구상해 준다.

바리케이드를 세울 수 있는 정점은, 정점 분할 내 엣지의 capacity를 그 바리케이드를 세우는데 드는 비용으로 한다.

source는 B이며, sink는 새로 만들어서 외각 모든 점들과 연결해 준다.

최대 유량이 $ \infty $이면 강도를 잡지 못하는 것이고, 그렇지 않으면 MFMC theorem을 이용해 최대 유량만큼의 비용으로 강도를 잡을 수 있다.

코드

---

import sys
from collections import deque

m, n, c = map(int, sys.stdin.readline().split())
board = [sys.stdin.readline().strip() for _ in range(n)]
cost = list(map(int, sys.stdin.readline().split()))

k = 2 * n * m + 1
graph = [[] for _ in range(k)]

for i in range(n):
    for j in range(m):
        if board[i][j] == 'B':
            if (i in [0, n - 1]) or (j in [0, m - 1]):
                print(-1)
                exit()
            
            start = m * i + j + m * n
            graph[start].append([m * (i - 1) + j, float('inf')])
            graph[start].append([m * i + j - 1, float('inf')])
            graph[start].append([m * (i + 1) + j, float('inf')])
            graph[start].append([m * i + j + 1, float('inf')])
            continue
        
        if board[i][j] == '.':
            if (i in [0, n - 1]) or (j in [0, m - 1]):
                graph[m * i + j].append([k - 1, float('inf')])
            
            if i and (board[i - 1][j] != 'B'):
                graph[m * i + j].append([m * (i - 1) + j, float('inf')])
            
            if (i < n - 1) and (board[i + 1][j] != 'B'):
                graph[m * i + j].append([m * (i + 1) + j, float('inf')])
            
            if j and (board[i][j - 1] != 'B'):
                graph[m * i + j].append([m * i + j - 1, float('inf')])
            
            if (j < m - 1) and (board[i][j + 1] != 'B'):
                graph[m * i + j].append([m * i + j + 1, float('inf')])

        else:
            graph[m * i + j].append([m * i + j + m * n, cost[ord(board[i][j]) - 97]])
            if (i in [0, n - 1]) or (j in [0, m - 1]):
                graph[m * i + j + m * n].append([k - 1, float('inf')])

            if i and (board[i - 1][j] != 'B'):
                graph[m * i + j + m * n].append([m * (i - 1) + j, float('inf')])
            
            if (i < n - 1) and (board[i + 1][j] != 'B'):
                graph[m * i + j + m * n].append([m * (i + 1) + j, float('inf')])
            
            if j and (board[i][j - 1] != 'B'):
                graph[m * i + j + m * n].append([m * i + j - 1, float('inf')])
            
            if (j < m - 1) and (board[i][j + 1] != 'B'):
                graph[m * i + j + m * n].append([m * i + j + 1, float('inf')])

ans = 0
while True:
    prev = [-1] * k
    queue = deque([(start, float('inf'))])
    while queue:
        cur, res = queue.popleft()
        
        for nxt, capacity in graph[cur]:
            if nxt == k - 1:
                res = min(res, capacity)
                prev[-1] = cur
                break
            
            if prev[nxt] == -1:
                prev[nxt] = cur
                queue.append((nxt, min(res, capacity)))

        if prev[-1] != -1:
            break
    
    if prev[-1] == -1:
        break
    
    if res == float('inf'):
        print(-1)
        exit()

    ans += res
    nxt = k - 1
    while nxt != start:
        cur = prev[nxt]
        for i in range(len(graph[cur])):
            if graph[cur][i][0] == nxt:
                graph[cur][i][1] -= res
                if graph[cur][i][1] == 0:
                    graph[cur].remove([nxt, 0])
                break
        
        for i in range(len(graph[nxt])):
            if graph[nxt][i][0] == cur:
                graph[nxt][i][1] += res
                break
        else:
            graph[nxt].append([cur, res])
        
        nxt = cur

print(ans)