상하수도 배관망을 설계하여 도시 전체에 물을 공급하거나, 꽉 막힌 도로망에서 차량의 흐름을 최적화하여 가장 많은 차를 통과시켜야 하는 상황을 상상해 보십시오. 각 파이프나 도로마다 한 번에 통과할 수 있는 '최대 용량(Capacity)'이 정해져 있을 때, "출발지(Source)에서 도착지(Sink)까지 초당 보낼 수 있는 가장 많은 물의 양(최대 유량, Maximum Flow)은 얼마인가?"라는 질문에 완벽한 해답을 제시하는 것이 바로 네트워크 플로우(Network Flow) 알고리즘입니다. 이 분야의 기초인 포드-풀커슨(Ford-Fulkerson) 방법론의 치명적인 약점을 완벽하게 보완하고, 어떤 악의적인 데이터가 들어와도 O(V * E^2)의 확정적인 속도를 보장하는 '에드몬드-카프(Edmonds-Karp) 알고리즘'의 놀라운 원리와 '음의 유량'이라는 천재적인 발상을 완벽하게 해부해 보겠습니다.
1. 네트워크 플로우의 기초와 포드-풀커슨의 한계
최대 유량을 구하는 가장 기본적인 아이디어는 "출발지에서 도착지까지 물이 흐를 수 있는 여유 경로(증강 경로, Augmenting Path)가 있다면, 그 경로의 최소 용량만큼 물을 계속 흘려보내자"는 것입니다. 더 이상 물이 흐를 수 있는 경로가 없을 때까지 이 과정을 반복하는 것이 포드-풀커슨(Ford-Fulkerson) 알고리즘입니다.
1-1. DFS의 치명적 함정
포드-풀커슨 알고리즘은 경로를 찾을 때 보통 깊이 우선 탐색(DFS)을 사용합니다. 하지만 DFS를 사용하면 끔찍한 비효율이 발생할 수 있습니다. 예를 들어, 위아래로 1,000의 용량을 가진 파이프가 있고, 그 사이를 가로지르는 용량 1짜리 얇은 파이프가 있다고 가정해 봅시다. DFS가 재수 없게 이 얇은 교차 파이프를 계속 왕복하는 경로만 찾아낸다면, 한 번에 1의 유량밖에 보내지 못해 무려 2,000번의 탐색을 반복해야만 최대 유량(2000)을 찾아내는 O(E * f) (f는 최대 유량)의 최악의 시간 복잡도에 빠지게 됩니다.
2. 에드몬드-카프 알고리즘: BFS를 통한 구원
1972년, 잭 에드몬드와 리처드 카프는 이 문제를 해결하기 위해 아주 간단하지만 위대한 규칙 하나를 추가했습니다. "경로를 찾을 때 무작정 파고드는 DFS를 버리고, 간선의 개수가 가장 적은 최단 경로를 찾는 너비 우선 탐색(BFS)을 사용하자!"
2-1. 왜 BFS가 정답일까?
BFS를 사용하여 물을 흘려보내면, 중간에 얇은 파이프를 통해 빙빙 돌아가는 비효율적인 경로를 원천 차단하고, 가장 직관적이고 굵직한 최단 경로(간선의 개수가 최소인 경로)부터 빠르게 물을 채워 넣게 됩니다. 수학적으로 증명된 바에 따르면, BFS를 사용할 경우 경로를 찾는 최대 횟수가 유량(f)의 크기와 상관없이 O(V * E)번으로 엄격하게 제한됩니다. 따라서 매번 BFS 탐색에 걸리는 시간 O(E)를 곱하여, 최종적으로 O(V * E^2)라는 유량 크기에 완벽히 독립적인 안정적인 시간 복잡도를 얻어내게 됩니다.
3. 네트워크 플로우의 마법: 음의 유량(Negative Flow)과 잔여 용량
이 알고리즘이 100% 최적의 정답을 찾아낼 수 있는 가장 핵심적인 비결은 바로 '유량의 상쇄(음의 유량)' 개념에 있습니다. 인간이 눈대중으로 물을 흘려보내다 보면, 초반에 잘못된 경로를 선택해서 나중에 더 많은 물을 보낼 수 있는 기회를 놓치는 실수(그리디의 한계)를 저지르게 됩니다. 에드몬드-카프 알고리즘은 이를 기계적으로 수정할 수 있는 타임머신을 제공합니다.
3-1. 역방향 간선의 생성 (잔여 네트워크)
A에서 B로 10만큼의 물을 흘려보냈다고 합시다. 알고리즘은 이때 "B에서 A로 -10만큼의 물을 다시 되돌려 보낼 수 있는 가상의 역방향 파이프"를 메모리 상에 몰래 만들어둡니다. (이를 잔여 용량, Residual Capacity라고 부릅니다.)
나중에 다른 경로를 탐색하다가 더 최적의 길을 발견했는데, 아까 A에서 B로 보낸 물 때문에 길이 막혀 있다면 어떨까요? 알고리즘은 아까 만들어둔 B에서 A로 가는 가상의 역방향 파이프를 타고 물을 거꾸로 흘려보냅니다. 이는 물리적으로 물이 거꾸로 흐르는 것이 아니라, "아까 A에서 B로 보냈던 물 10을 취소(상쇄)하고, 그 물을 다른 최적의 경로로 돌려버린다"는 완벽한 논리적 수정을 의미합니다. 이 '음의 유량'을 통한 자가 수정 능력 덕분에, 알고리즘은 어떤 순서로 파이프를 채우든 간에 항상 100% 완벽한 최대 유량을 수학적으로 도출해 냅니다.
1. 네트워크 플로우(최대 유량) 문제는 출발지에서 도착지까지 파이프의 용량을 초과하지 않으면서 가장 많은 유량을 보내는 방법을 찾는 알고리즘입니다.
2. 기존 포드-풀커슨의 DFS 방식이 가진 최악의 비효율을 막기 위해, 너비 우선 탐색(BFS)을 도입하여 간선 수가 가장 적은 경로만 고집하는 것이 에드몬드-카프(Edmonds-Karp) 알고리즘입니다.
3. 탐색 과정에서 잘못된 선택을 언제든 번복할 수 있도록, 물이 흐른 반대 방향으로 음의 유량(역방향 잔여 간선)을 생성하여 물길을 수정하는 것이 알고리즘 최적화의 심장입니다.