[BOJ 3666] 리스크

문제

---

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

풀이

---

flow network 구상부터 parametric search를 사용하는 아이디어까지, 다이아 4에 걸맞는 문제였다.

적국과 인접한 지역들에 있는 병력의 최솟값의 최댓값을 구하는 문제다.

우선 source와 1~n번 노드들을 초기 군대 수를 capacity로 연결시켜준다.

그리고 한 턴 뒤의 1~n번 노드들을 sink로 연결시켜주는데, 적국과 인접하지 않은 지역은 capacity 1로 연결해도 충분하다.

문제는 적국과 인접한 지역들이다.

이렇게 ‘최솟값의 최댓값’ 등을 구하는 문제엔, 정답을 고정시키고 참 거짓 여부를 가리며 범위를 좁혀나가는 매개 변수 탐색법이 효과적이다.

그러므로 적국과 인접한 지역들은 상수 mid로 capacity를 통일한 후 sink에 이어준다.

나머지 노드들 간의 엣지는, 인접한 두 아군 지역에 대해 capacity 무한대로 연결시켜주면 된다.

물론 병력을 이동시키지 않을 수도 있기 때문에, 같은 번호의 한 턴 뒤 노드에도 capacity 무한대로 연결시켜준다.

이렇게 구성한 flow network에서 최대 유량을 구한 후, sink로 흘러들어가는 간선들의 flow가 모두 포화 상태라면 이 mid 값은 유효한 것이다.

코드

---

import sys
from copy import deepcopy
from collections import deque

for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    army = list(map(int, sys.stdin.readline().split()))
    board = [sys.stdin.readline().strip() for __ in range(n)]

    graph_ = [[0] * (2 * n + 2) for __ in range(2 * n + 2)]

    for i in range(n):
        if army[i]:
            graph_[0][i + 1] = army[i]
            graph_[i + 1][i + n + 1] = float('inf')
            graph_[i + n + 1][-1] = 1
            for j in range(i + 1, n):
                if board[i][j] == 'Y':
                    if army[j]:
                        graph_[i + 1][j + n + 1] = float('inf')
                        graph_[j + 1][i + n + 1] = float('inf')

    left = 1
    right = 9802
    while left <= right:
        mid = (left + right) // 2

        graph = deepcopy(graph_)

        for i in range(n):
            if not army[i]:
                for j in range(n):
                    if (board[i][j] == 'Y') and army[j]:
                        graph[j + n + 1][-1] = mid

        total = 0
        while True:
            prev = [-1] * (2 * n + 2)
            queue = deque([(0, float('inf'))])
            while queue:
                cur, res = queue.popleft()

                for nxt in range(1, 2 * n + 2):
                    if (nxt == 2 * n + 1) and graph[cur][-1]:
                        res = min(res, graph[cur][-1])
                        prev[-1] = cur
                        break

                    if (prev[nxt] == -1) and graph[cur][nxt]:
                        prev[nxt] = cur
                        queue.append((nxt, min(res, graph[cur][nxt])))

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

            total += res
            while nxt:
                cur = prev[nxt]
                graph[cur][nxt] -= res
                graph[nxt][cur] += res
                nxt = cur
        
        flag = 0
        for i in range(n):
            if army[i]:
                flag += graph[i + n + 1][-1]
        
        if flag:
            right = mid - 1
        else:
            left = mid + 1
    
    print(right)