문제 정보
- https://www.acmicpc.net/problem/32582
- 최대 유량(?), 수학
문제 정리
양들이 목장 안으로 들어온 늑대를 피해 도망치고 있다. 목장에는 울타리로 둘러싸인 통로들이 있으며, 이 통로들이 서로 연결되어 최종적으로 농장 마당으로 이어지는 하나의 출구에 도달한다.
통로의 배치는 삼각형을 두 개 이어붙인 모양을 하나의 세그먼트라고 하며, 이런 세그먼트가 여러 개 직렬로 연결되어 있다.
각 통로의 중간에는 자동 게이트가 있어 정해진 수의 양만 통과시키고 닫혀 버리며 더 이상 해당 통로를 이용할 수 없다. 또한, 어떤 통로에서도 양 두마리가 서로 반대 방향으로 뛰는 일은 없다.
이 때, 탈출할 수 있는 양의 최대 수를 구해야 한다.
풀이
내가 이 문제에서 한 관찰은 크게 3가지이다.
- 최대 유량으로 모델링 가능.
- 각 통로를 간선, 게이트가 허용하는 양의 수를 간선의 용량으로 볼 경우, 이 문제는 시작점에서 도착점까지 보낼 수 있는 양의 최대값을 세는 최대 유량 문제로 볼 수 있다.
- 각 세그먼트로 분리 가능.
- 세그먼트는 서로 직렬 연결이므로, 전체 최대 유량은 각 세그먼트에서 가능한 최대 유량의 최소값이 된다. 즉, 세그먼트를 각각 분리해서 계산해도 무방하다.
- 최대 유량 최소 컷 정리
- 세그먼트의 모양이 간단하기 때문에 "그래프의 최대 유량은 그래프를 둘로 나누는 최소 컷의 비용과 같다"는 최대 유량 최소 컷 정리를 알고 있다면, 눈으로 충분히 그래프의 최소 컷을 계산할 수 있다.
후기
딱 봐도 유량 문제인데 일단 Edmonds-Karp 알고리즘부터 박아보자 해서 332ms로 AC를 받았고, 최대 유량 최소 컷 정리를 이용해 각 세그먼트 별로 min() 계산만 남겼더니 132ms까지 런타임이 줄었다.
사실 "최대 유량"이나 "최대 유량 최소 컷 정리"같은 경우 플래티넘 티어의 알고리즘이긴 한데, 그 알고리즘을 직접 쓰는게 아니라 지식만 사용해서 풀 수 있으니 골드로 기여해도 괜찮지 않을까?
코드
# 백준 32582
import io
input = io.BufferedReader(io.FileIO(0), 1<<18).readline
INF = 10**9
def solve(A, B, C, D, E):
return min(A+D, B+E, B+C+D, A+C+E)
def main():
N = int(input())
maxSheep = INF
for _ in range(N):
A, B, C, D, E = map(int, input().split())
maxSheep = min(maxSheep, solve(A, B, C, D, E))
print(maxSheep)
main()
