1. 문제 설명
https://www.acmicpc.net/problem/6086
6086번: 최대 유량
첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위
www.acmicpc.net
진짜 처음 보는 알고리즘이었는데 너무너무너무 어려웠다.
하루 온종일 이것만 보다가 너무 화나서 그냥 알고리즘과 흐름을 전부 외워버렸더니 오히려 좀 이해가 되는 기분.
2. 아이디어
에드몬드 카프 알고리즘이라고 최대 유량에서 곧잘 쓰이는 유명한 알고리즘이다.
정점을 알파벳으로 주기 때문에 ASCII 코드값을 참조해 값을 다루어야 한다. (man ascii)
그러면 일단 정점과 정점을 연결해주는 것까지 해주면 된다.
(정말 중요한 건 역방향까지 고려해야 함.)
그 다음에 해야하는 작업은 탐색과 업데이트인데,
유량은 결국 최소값이 지배하게 되므로 최소값을 찾아 현재 상태를 업데이트 해주어야 한다.
그래프에서 탐색..여기서는 BFS를 쓴다.
탐색을 할 완성된 그래프와 중복 방문을 방지하기 위한 visited 리스트를 준비한다.
그런데 visited가 단순 방문 여부를 알아주는 역할에서 그만이 아니라 현재 노드의 부모 노드를 확인까지
할 수 있다. 즉, 방문값으로 부모의 아스키 코드 넘버값을 던져주어야 한다는 뜻이다.
아래에 있는 표는 각각 부모에서 자식으로 흐르는 실제 유량의 값인데 왜 이차원 배열인지는 이후 설명.
파이프의 용량과는 별개의 값이다. 정말 실제로 얼마나 흐르고 있는지를 확인하기 위함.
source는 언제나 A, sink는 언제나 Z이므로 DFS 시작 노드 또한 A를 기준으로 하며,
visited가 Z까지 도달하지 않은 경우에는 최대 유량 탐색을 break하면 된다.
파이프에 연결된 수는 흐를 수 있는 최댓값이고 아직 유량 정보는 업데이트 한 적이 없다.
D->Z는 비록 연결되어 있지만 Z가 이미 B와 연결되어 있으므로 이번 탐색에서는
해당 경로를 통해서 방문할 수 없다.
이제 역방향으로 되돌아가면서 파이프의 최대 용량을 확인한다.
돌아가는 방법은 아까 체크한 visited를 통해 부모 노드를 확인하면서 거슬러 간다.
(지금은 보기 좋게 하기 위해 실제 유량에 값을 넣고 있지만 실제로는 아직 할당하지 않음.)
B에서 A로 가보니 6보다 더 작은 파이프가 나타났다. 그럼 min_value값으로 3을 저장하고 반복을 멈춘다.
어 근데 B랑 C는 탐색을 안 하나요?
B랑 C는 이번 탐색에서 Z와 이어지지 않았기 때문에 탐색이 불가능하다.
물론 그렇다고 해서 다음에는 반복이 가능한 것도 아니다. 이유는 다음과 같다.
처음 visited를 갱신할 때 언급하지 않았지만 사실 이 과정에서는 한 가지 조건이 들어있다.
현재 파이프에 더 유량이 흐를 수 있을 때만 다음 노드로 이동이 가능하다.
문제는 A에서 B로 가는 파이프는 이미 3만큼 흘려버렸기 때문에 더이상 최대 유량이고 뭐고
이게 답이 되어버린 것이다.
만약 D를 통해 Z로 이동하는 유량을 확인해보고 싶다면 B-6-Z를 B-2-Z로 바꿔버리면
다음 단계로 넘어간다.
B-2-Z인 경우
이 경우에는 첫 번째 탐색에서 최소 유량이 B-2-Z에 의해 결정되어버렸기 때문에 A-B 파이프에는 1만큼
더 흐를 수 있는 용량이 존재한다. 따라서 정상적으로 DFS가 돌아가고 D-Z 파이프를 경유하게 된다.
자 그렇다면 다른 건 이해가 되는데 대체 음수값은 왜 저장을 해야하는 걸까?
다음 케이스를 살펴보자
A에서 Z까지 흐르는 최대 유량은 당연히 2가 되어야 맞지만, 빨간색의 경로로 먼저 흘러가버리면
A-C-Z를 경유하는 파이프가 막히므로 최대 유량이 1밖에 나오지 않는다.
그러면 여기서 탐색을 멈추고 반복문이 끝나버리므로 이 난제를 해결할 필요가 생겼는데
그것이 바로 역간선에 음수값을 추가해 "유령 간선"을 만들어 버리는 것이다.
실제로는 존재할 수 없는 흐름인데, 유령간선에 의해 C-B 사이의 유량 흐름이 상쇄됨으로써 답이 나온다.
더 명확하게 설명을 해놓고 싶지만, 이 부분은 나도 알다가도 헷갈려서 좀 더 공부해야 이해할 수 있을 거 같다.
일단 그냥 외워버리고 넘어가는 게 편하다.
3. 코드
'''
1. 가능한 경로와 경로상의 최소 유량 찾기
(1) bfs (에드몬드 카프 알고리즘)
(2) 탐색조건: 현재 flow가 해당 간선의 최대 flow를 넘지 않았는가?
visited가 갱신되지 않았는가? -> 종점이 아니라면 큐 탈출
(3) 최소유량: 경로상에 있는 간선의 용량 중 가장 작은 것을 택한다.
2. 현재 상태를 업데이트
(1) 가장 작은 유량을 찾아서 전체 유량 수정
(2) 이때, 역순으로 흐르는 방향은 -값으로 수정해야 한다.
=> 경로의 순서에 따라 최대로 흐르지 않았음에도 불구하고 끝나버리기 때문이다.
3. 더이상 가능한 경로가 존재하지 않을 때까지 반복한다.
'''
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
def bfs(start, process, flow):
queue = deque()
queue.append(start)
visited = [-1] * 128
visited[start] = start
while queue:
idx = queue.popleft()
for i in range(65, 123):
if visited[i] == -1 and process[idx][i] - flow[idx][i] > 0:
queue.append(i)
visited[i] = idx
return visited
def merge_pipe(process):
start, end = 65, 90
flow = [[0]*128 for _ in range(128)]
result = 0
while True:
parent = bfs(start, process, flow)
if parent[end] == -1:
return result
min_value = 2147483647
idx = end
while idx != start:
min_value = min(min_value, process[parent[idx]][idx] - flow[parent[idx]][idx])
idx = parent[idx]
idx = end
while idx != start:
flow[parent[idx]][idx] += min_value
flow[idx][parent[idx]] -= min_value
idx = parent[idx]
result += min_value
def solution():
n = int(input())
process = [[0]*128 for _ in range(128)]
for _ in range(n):
u, v, x = input().split()
u = ord(u)
v = ord(v)
x = int(x)
process[u][v] += x
process[v][u] += x
print(merge_pipe(process))
solution()