BOJ 16407 - Cops and Robbers 링크
(2023.07.24 기준 P2)

문제

m × n 행렬이 주어지며 'B'인 칸에서 바깥쪽으로 나가지 못하게끔 막아야 한다.
막는 방법은 소문자인 칸에 바리게이트를 설치할 수 있으며 각 소문자 별로 바리게이트를 설치하는 비용이 주어진다.
이 때, 나가지 못하게끔 설치하는 바리게이트 비용의 최소 비용 출력

알고리즘

MFMC

풀이

문제는 결국 'B'인 칸에서 바깥쪽으로 나갈 수 있는 최대 유량을 구해야 하는 것이다. 바리게이트 비용을 용량이라고 가정하면, 결국 바깥쪽으로 흐르는 최대 유량이 곧 최소로 설치해야하는 바리게이트의 비용이 되기 때문이다.

예제 3번을 예로 들면, 그래프 모델링은 다음과 같이 하면 된다. 기본 간선의 용량은 전부 inf로 잡으면 된다.

분할된 정점끼리 잇는 간선의 용량은 바리게이트의 비용(설치할 수 없는 곳이면 inf),
가장 바깥쪽에 있는 칸은 sink로 연결, 인접한 칸끼리 연결하면 된다.

그리고 유량이 계속 늘어나면 못막는다는 의미가 되므로 -1을 출력하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30, MAXL = MAXN * MAXN * 2 + 1;
const int inf = 1e10;

int n, m, c, o, cost[26];
string matrix[MAXN];

vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int coord(int i, int j){
    return i * n + j;
}

struct Dinic{
    int source, sink, length, capacity[MAXL][MAXL], lv[MAXL], work[MAXL];
    vector<int> connect[MAXL];

    void init();

    void add_edge(int u, int v, int w = 1){ // 단방향
        connect[u].push_back(v);
        connect[v].push_back(u);
        capacity[u][v] = w;
    }

    bool _bfs(){
        lv[source] = 0;
        queue<int> q; q.push(source);
        while (!q.empty()){
            int here = q.front(); q.pop();
            for (auto there: connect[here])
                if (capacity[here][there] && !~lv[there]){
                    lv[there] = lv[here] + 1;
                    q.push(there);
                }
        }
        return ~lv[sink];
    }

    int _dfs(int here, int f){
        if (here == sink) return f;
        for (int i = work[here], sz = connect[here].size(); i < sz; i++){
            int there = connect[here][i];
            if (capacity[here][there] && lv[there] == lv[here] + 1){
                int result = _dfs(there, min(f, capacity[here][there]));
                if (result){
                    capacity[here][there] -= result;
                    capacity[there][here] += result;
                    work[here] = i;
                    return result;
                }
            }
        }
        work[here] = connect[here].size();
        return 0;
    }

    int flow(){
        int result = 0;
        while (true){
            fill(lv, lv + length, -1);
            if (!_bfs()) break;
            fill(work, work + length, 0);
            while (true){
                int f = _dfs(source, inf);
                if (!f) break;
                result += f;
                if (result > 1e9) // 유량이 끝도 없이 늘어난다면 막을 수 없는 것이다.
                    return -1;
            }
        }
        return result;
    }
    
}dinic;

void Dinic::init(){
    sink = o * 2; length = sink + 1;
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
        if (matrix[i][j] == 'B') source = coord(i, j) + o;

    fill(&capacity[0][0], &capacity[length - 1][length], 0);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> c;
    for (int i = 0; i < m; i++) cin >> matrix[i];
    for (int i = 0; i < c; i++) cin >> cost[i];

    // [0, m*n) : 칸, [m*n, m*n*2) : 정점 분할된 칸, m*n*2 : sink
    o = m * n;
    dinic.init();

    // 각 칸마다 간선을 추가
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++){
        int here = coord(i, j);

        // 정점 분할
        if (matrix[i][j] - 'a' >= 0) // 바리게이트를 설치할 수 있는 소문자이면 용량은 cost
            dinic.add_edge(here, here + o, cost[matrix[i][j] - 'a']);
        else // 아니면 용량은 inf
            dinic.add_edge(here, here + o, inf);

        // 현재 칸이 가장 바깥쪽에 있는 칸이면 sink와 연결
        if (!i || i == m - 1 || !j || j == n - 1)
            dinic.add_edge(here + o, dinic.sink, inf);

        // 인접한 칸과 연결
        for (auto [di, dj]: dir) if (0 <= i + di && i + di < m && 0 <= j + dj && j + dj < n){
            int there = coord(i + di, j + dj);
            dinic.add_edge(here + o, there, inf);
        }
    }

    cout << dinic.flow();
}

• Python

import sys; input = sys.stdin.readline
from math import inf
from collections import deque

dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def coord(i, j):
    return i * n + j

class Dinic:
    def __init__(self):
        self.sink = o * 2
        self.length = self.sink + 1
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 'B':
                    self.source = coord(i, j) + o

        self.connect = [[] for _ in range(self.length)]
        self.capacity = [[0] * self.length for _ in range(self.length)]

    def add_edge(self, u, v, w): # 단방향
        self.connect[u].append(v)
        self.connect[v].append(u)
        self.capacity[u][v] = w

    def _bfs(self):
        self.lv[self.source] = 0
        queue = deque([self.source])
        while queue:
            here = queue.popleft()
            for there in self.connect[here]:
                if self.capacity[here][there] and not ~self.lv[there]:
                    self.lv[there] = self.lv[here] + 1
                    queue.append(there)
        return ~self.lv[self.sink]

    def _dfs(self, here, f):
        if here == self.sink:
            return f
        for i in range(self.work[here], len(self.connect[here])):
            there = self.connect[here][i]
            if self.capacity[here][there] and self.lv[there] == self.lv[here] + 1:
                result = self._dfs(there, min(f, self.capacity[here][there]))
                if result:
                    self.capacity[here][there] -= result
                    self.capacity[there][here] += result
                    self.work[here] = i
                    return result
        self.work[here] = len(self.connect[here])
        return 0

    def flow(self):
        result = 0
        while True:
            self.lv = [-1] * self.length
            if not self._bfs():
                break
            self.work = [0] * self.length
            while True:
                f = self._dfs(self.source, inf)
                if not f:
                    break
                result += f
                if result > 1e9: # 유량이 끝도 없이 늘어난다면 막을 수 없는 것이다.
                    return -1
        return result

n, m, c = map(int, input().split())
matrix = [input().strip() for _ in range(m)]
cost = list(map(int, input().split()))

# [0, m*n) : 칸, [m*n, m*n*2) : 정점 분할된 칸, m*n*2 : sink
o = m * n
dinic = Dinic()

# 각 칸마다 간선을 추가
for i in range(m):
    for j in range(n):
        here = coord(i, j)

        # 정점 분할
        if matrix[i][j].islower(): # 바리게이트를 설치할 수 있는 소문자이면 용량은 cost
            dinic.add_edge(here, here + o, cost[ord(matrix[i][j]) - 97])
        else: # 아니면 용량은 inf
            dinic.add_edge(here, here + o, inf)

        # 현재 칸이 가장 바깥쪽에 있는 칸이면 sink와 연결
        if not i or i == m - 1 or not j or j == n - 1:
            dinic.add_edge(here + o, dinic.sink, inf)

        # 인접한 칸과 연결
        for di, dj in dir:
            if 0 <= i + di < m and 0 <= j + dj < n:
                there = coord(i + di, j + dj)
                dinic.add_edge(here + o, there, inf)

print(dinic.flow())