1. 최대 유량(Network Flow) 문제
최대 유량 문제는 유량이 시작되는 소스(source)와 유량이 도착하는 싱크(sink)가 존재하는 그래프에서 최대로 생성될 수 있는 유량을 찾는 문제입니다. 그래프의 간선들을 타고 유량이 흐르는데 보통 방향 그래프가 다뤄지는 경우가 많으나 방향이 없는 그래프가 주어지기도 합니다. 각 간선들은 흐를 수 있는 유량의 제한인 용량(capacity)이 있습니다.
이 문제를 해결할 수 있는 방법을 처음 제안한 두 사람의 이름을 딴 포드-풀커슨 알고리즘이 있습니다. 이 알고리즘은 방법론에 대한 내용이고 에드몬드-카프 알고리즘에서 O(VE^2)의 BFS를 통한 유량의 증가 경로 탐색 방법이 제시되었습니다. 이후 레벨 그래프를 활용해 O(V^2E)로 개선한 디닉(디니츠) 알고리즘이 등장하게 되었습니다.
에드몬드-카프 알고리즘은 구현의 편의성이 뛰어나다는 장점이 있지만 간선의 제곱이라는 실행 시간의 부담이 있습니다. 반면 디닉 알고리즘은 정점에 제곱으로 훨씬 빠른 성능을 자랑하지만 실행 과정이 복잡해 구현이 간단하지 않습니다.
2. 특수한 문제 상황
최대 유량 문제는 파이프라인의 유체 공급량 계산, 네트워크의 데이터 전송량, 물류 흐름 최적화, 교통 제어 등에 활용됩니다. 하지만 문제 정의에 따르면 유량(유체, 데이터, 물류, 교통량 등)의 최대 용량은 간선(파이프, 케이블, 컨베이어벨트, 도로 등)에만 존재하지만 실제 상황에서는 정점에도 용량 제한이 있는 경우(탱크, 서버, 물류센터, 교차로 등)가 일반적입니다. 따라서 실제 상황을 최대 유량 문제로 모델화 하기 위해서는 간선 뿐만 아니라 정점에도 용량의 제한을 두는 특수한 테크닉이 필요합니다.
1) 정점 분할
간선에 용량이 있는 그래프의 정점 하나를 살펴봅시다. v에는 2개의 진입 간선을 타고 총 8의 유량이 유입될 수 있습니다. 그리고 3개의 진출 간선을 타고 최대 7의 유량이 유출될 수 있습니다. 이렇게 두고 보면 v에 있는 유량 제한은 7이라고 생각될 수 있습니다. 이 제한은 순전히 v의 진출 간선 용량에 의해 결정된 것이기 때문에 실제로 v에 용량 제한이 있다면 문제가 발생할 수 있습니다. 그럼 v를 다음 그림과 같이 분리해보겠습니다.
v와 v'로 분리시켜 두 정점을 연결했습니다. 어차피 유량은 한 방향으로만 흐르기 때문에 v만 있어도, v에 v'를 연결해도 유량의 방향은 변함이 없습니다. 이때 v-v'간선에 용량이 있다면 이 간선 용량이 정점 v의 용량이 됩니다. 어떤 정점에 용량이 필요한 경우, 이와 같은 방법으로 정점을 분리해 간선 하나로 연결하고 용량을 부여하면 됩니다. 만약 교차로를 정점으로 표현한 경우, 한 차례의 신호에 직진할 수 있는 차량의 수와 좌회전할 수 있는 차량의 수가 다를 수 있습니다. 이런 경우는 정점을 3개로 분할해 직진 차량의 용량과 좌회전 차량의 용량을 따로 부여하는 것도 가능합니다.
2) 용량이 1인 정점 분할
N명의 사람이 M개의 선택지를 놓고 선택하는 문제상황을 생각해봅시다. 1명의 사람이 1개의 선택만 할 수 있으며 각 사람이 선택할 수 있는 경우가 제한되었다면 이 상황을 모든 용량이 1인 방향 그래프로 그릴 수 있습니다. 이 문제는 이분 매칭으로 해결할 수 있지만 최대 유량으로도 해결할 수 있습니다. 소스를 생성하고 소스에서 모든 사람에게 용량 1인 간선을 연결하고, 싱크를 생성하고 M개의 선택지에서 싱크로 용량 1인 간선을 연결한 다음 각 사람의 선택지들을 모두 용량이 1인 간선으로 각각 선택지와 연결해주면 소스에서 싱크로 도착할 수 있는 최대 유량이 곧 선택지를 고를 수 있는 최대 사람 수가 됩니다.
여기서 문제를 조금 바꿔봅시다. 소스에 연결된 정점에서 싱크로 연결된 정점으로 곧장 이어지는 게 아닌 중간에도 몇 정점들이 있다고 해보겠습니다.
이런 문제 상황은 물류센터 S에서 출발해 3명의 배송 기사가 a~j까지의 정점에 도달하고 물류센터인 T로 복귀하는 문제로 생각할 수 있습니다. 두 명의 배송 기사가 같은 지역에 도착하는 건 비효율적이기 때문에 각 배송 기사는 서로 겹치지 않는 경로를 따라 T에 도달할 수 있어야 합니다. 문제는 정점 a같은 부분에서 발생합니다.
배송 기사 1과 3이 이와 같은 경로를 선택한다면 용량 제한의 문제 없이 S-1-a-d-, S-3-a-c-와 같은 경로를 선택할 수 있게 됩니다. 모든 정점은 최대 1명의 배송 기사만 도착할 수 있어야 합니다. 이런 경우, 정점 a를 분리하고 용량을 1로 제한하면 1가지의 유량만 유입되도록 제어할 수 있습니다.
위 그림과 같이 정점을 분할하고 용량을 1로 제한하게 되면 해당 정점은 1의 유량만 진입할 수 있게 됩니다. a~j의 모든 정점에 대해 똑같은 정점 분할을 해놓는다면 1명의 배송 기사만이 해당 정점의 간선을 통과할 수 있고 모든 유량이 싱크에 도달했을 때 각 유량이 생성한 경로는 소스와 싱크를 제외한 어떤 간선과 정점도 공유하지 않고 분리됩니다.
3) 유량의 경로 탐색
2)에서 서술한 소스와 싱크를 제외한 모든 간선과 정점의 용량이 1인 문제 상황에서 각 유량이 소스에서 싱크에 도달하는 경로가 필요할 수 있습니다. 이걸 추적하는 방법을 생각해봅시다. 우선 증가 경로를 찾는 과정에서 음의 유량을 가진 경로가 포함될 때가 중요합니다. 다음 탐색 과정을 살펴봅시다. route 배열은 각 정점이 다음으로 가리키는 정점을 의미합니다.
먼저 정점 번호에 의해 증가경로 S-1-2-3-4-5-T가 탐색되고 유량 1이 생성됩니다. route 배열도 경로에 따라 바뀝니다. 이건 유량을 생성할 때 처리할 수 있습니다.
이제 다음 간선을 탐색합니다. S에서 6, 6에서 유량이 남은 간선은 없지만 음의 유량을 가진 3-2가 있습니다. 마찬가지 음의 유량을 가진 5-4를 따라가면 증가경로 S-6-3-2-5-4-T가 탐색됩니다.
이제 여기서 route를 갱신하는 과정이 매우 중요합니다.
- S에서 6은 탐색된 적이 없으니 route[0] = 6으로 갱신합니다.
- 6에서 3은 탐색된 적이 없으니 route[6] = 3으로 갱신합니다.
- 3에서 2는 음의 유량을 탐색했으므로 건드리지 않습니다. (route[3] = 4 유지)
- 2에서 5는 탐색된 적이 없으니 route[2] = 5로 갱신합니다.
- 5에서 4는 음의 유량을 탐색했으므로 건드리지 않습니다. (route[5] = 7 유지)
- 4에서 T는 탐색된 적이 없으니 route[4] = 7로 갱신합니다.
이제 소스에 연결된 정점을 출발 지점으로 두고 route 배열 위의 값을 인덱스로 따라가다 보면 유량이 생성되어있는 모든 증가 경로를 다 탐색할 수 있습니다.
이 글에서 서술한 방법으로 풀 수 있는 문제: 백준 7616번 교실로 가는 길
