알고리즘 공부
네트워크 플로우(Network Flow)
네트워크 플로우의 개념과 에드몬드-카프 알고리즘을 통해 최대 유량 문제를 해결해봅니다.
🔍 네트워크 플로우(Network Flow)
네트워크 플로우는 한 노드에서 다른 노드로 흘러갈 수 있는 최대 흐름량을 구하는 알고리즘으로 이러한 알고리즘이 적용되는 문제를 최대 유량 문제라고도 합니다.
위 알고리즘에서 다루는(입력으로 들어오는) 자료구조는 유향 가중치 그래프로, 이와 함께 source 노드와 sink 노드 정보를 알고 있어야 합니다. 두 노드를 조금 더 살펴보면 다음과 같습니다.
Source 노드: 진입 간선이 없는(진입 차수 = 0) 노드
Sink 노드: 진출 간선이 없는(진출 차수 = 0) 노드
예를 들어, 다음과 같은 그래프의 경우
┌───┐ 6 ┌───┐
│ 2 │ ────→ │ 3 │
5 └───┘ └───┘ 5
↗ ↑ │ ↘
┌───┐ │ │ ┌───┐
│ 1 │ 3 │ 8 │ │ 6 │
└───┘ │ │ └───┘
↘ │ ↓ ↗
4 ┌───┐ ┌───┐ 2
│ 4 │ ────→ │ 5 │
└───┘ 1 └───┘노드 1이 source 노드가 되고 노드 6이 sink 노드가 됩니다.
최대 유량 문제 조금 더 살펴보기
최대 유량 문제에서 우리의 일은 source 노드로부터 sink 노드로까지 최대한의 유량을 흘려 보내는 것입니다.
최대 유량 문제의 그래프에서 간선들의 가중치는 해당 간선에 최대로 흐를 수 있는 용량을 나타내며, 각 중간 노드로 들어오는 유량과 나가는 유량의 크기는 같아야 합니다.
위의 예시에서는 최대 유량의 크기는 7이며 아래는 흐름의 예시입니다.
┌───┐ 6/6 ┌───┐
│ 2 │ ────→ │ 3 │
3/5 └───┘ └───┘ 5/5
↗ ↑ │ ↘
┌───┐ │ │ ┌───┐
│ 1 │ 3/3 │ 1/8 │ │ 6 │
└───┘ │ │ └───┘
↘ │ ↓ ↗
4/4 ┌───┐ ┌───┐ 2/2
│ 4 │ ────→ │ 5 │
└───┘ 1/1 └───┘간선마다 표시된 v/k의 의미는 용량 k의 간선에 유량이 v만큼 존재한다는 의미입니다.
위의 예시를 통해 우리는 source 노드에서 흘려보낸 유량의 총합(3 +4)과 sink 노드로 흘러들어온 유량의 총합(5 + 2)은 같다는 사실을 알 수 있습니다.
이러한 최대 유량 문제를 해결하기 위한 알고리즘들은 다음과 같습니다.
포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm): 해결에 DFS를 활용
에드몬드-카프 알고리즘(Edmonds-Karp Algorithm): 해결에 BFS를 활용
이 글에서는 일반적으로 효율이 더 좋다고 알려진 에드몬드-카프 알고리즘에 대해 살펴보겠습니다.
에드몬드-카프 알고리즘
에드몬드-카프 알고리즘은 빈 흐름에서 시작하여 단계를 거쳐나가며 source 노드에서 sink 노드로 흐르는 유량을 증가시키는 경로를 찾아나갑니다.
이때, 유량을 더 이상 증가시킬 수 없다면 최대 유량을 발견한 것입니다.
알고리즘이 진행되면 갱신되는 그래프 간선의 가중치는 해당 간선에 추가적으로 흐를 수 있는 유량을 의미합니다.
➡️ 초기 값은 해당 간선에 흐를 수 있는 흐름의 최대 용량
에드몬드-카프 알고리즘은 입력받은 유향 가중치 그래프에 추가적으로 각각의 간선에 대한 반대 방향 간선을 추가하고 0으로 초기화합니다.
➡️ 나중에 이 역간선의 가중치 값만큼 흘려보낸 유량을 취소할 수 있음.
➡️ 간선을 통해 흘려보낸 유량의 크기를 역간선에 음의 값으로 표현하여 추후 가능한 모든 경로를 탐색하는데 활용
위의 예시와 함께 이를 도식화하면 다음과 같습니다.
6
┌───┐ ────→ ┌───┐
│ 2 │ │ 3 │
└───┘ ←──── └───┘
5 ↗↙ 0 ↑│ 0 ↑│ 0 ↖↘ 5
┌───┐ ││ ││ ┌───┐
│ 1 │ 3 ││ 0 0 ││ 8 │ 6 │
└───┘ ││ ││ └───┘
0 ↖↘ 4 │↓ 1 │↓ 2 ↗↙ 0
┌───┐ ────→ ┌───┐
│ 4 │ │ 5 │
└───┘ ←──── └───┘
0에드몬드-카프 알고리즘은 다음과 같은 과정을 반복합니다.
BFS를 통해 source 노드에서 sink 노드로 이어지는 경로(경로 내 모든 간선의 잔여 용량 > 0)를 찾는다.
이러한 경로가 여러 개 존재하는 경우 아무거나 하나를 선택한다.
경로가 선택되었다면, 해당 경로를 구성하는 간선의 잔여 용량 중 최소 값 x만큼 유량이 증가한다.
➡️ 즉, 해당 경로의 간선들은 각각 x만큼 유량이 증가
방금 유량이 증가한 경로의 역간선(처음에 0으로 초기화한)들의 유량을 x만큼 감소시킨다.
방금의 경로는 용량이 가득 찬 간선(가중치 = 0)인 간선이 발생했으므로, 1로 돌아가 이러한 경로가 없을 때까지 과정을 반복한다.
⌨️ C++ 구현 코드
#include <bits/stdc++.h>
#define MAXN 100
#define INF 1000000000
using namespace std;
int N, M;
int source, sink;
int capacity[MAXN][MAXN], flow[MAXN][MAXN], before[MAXN];
vector< vector<int> > edges(MAXN);
int find_max_flow(){
int ans = 0, min_capacity;
queue<int> bfs;
while(1){
bfs.push(source);
for(int i=1;i<=N;i++) before[i] = -1;
while(!bfs.empty()){
int node = bfs.front();
for(int i=0;i<(int)edges[node].size();i++){
int next = edges[node][i];
if(capacity[node][next] - flow[node][next] > 0 && before[next] == -1){
bfs.push(next);
before[next] = node;
if(next == sink) break;
}
}
bfs.pop();
}
while(bfs.size()) bfs.pop();
if(before[sink] == -1) break;
min_capacity = INF;
for(int i=sink;i!=source;i=before[i]) {
min_capacity = min(min_capacity, capacity[before[i]][i] - flow[before[i]][i]);
}
for(int i=sink;i!=source;i=before[i]){
flow[before[i]][i] += min_capacity;
flow[i][before[i]] -= min_capacity;
}
ans += min_capacity;
}
return ans;
}
int main()
{
int a, b, c;
scanf("%d %d", &N, &M);
for(int i=0;i<M;i++){
scanf("%d %d %d", &a, &b, &c);
edges[a].push_back(b);
edges[b].push_back(a);
capacity[a][b] = c;
}
scanf("%d %d", &source, &sink);
printf("%d\n", find_max_flow());
}📚 참고 문헌
Competitive Programmer’s Handbook ― Chapter 20: Flows and cuts