참조
자료
영상
최대 유량
최대 유량(maximum flow) 문제에서는 두 개의 특별한 노드가 있는 방향 그래프를 다룬다. 소스(source) 는 들어오는 간선이 없는 노드이고, 싱크(sink) 는 나가는 간선이 없는 노드이다. 문제의 목적은 소스에서 싱크로 흐르는 유량을 최대한으로 만드는 것이다. 각각의 간선마다 흐를 수 있는 유량의 최대 용량이 정해져 있으며, 각각의 중간 노드로 들어오는 유량과 나가는 유량이 같아야 한다.
그림 17에 나와 있는 1번 노드가 소스이고 6번 노드가 싱크인 그래프를 예로 들어 생각해 보자. 이 그래프의 최대 유량은 그림 18에 나온 것과 같이 7이다. 표기는 용량이 인 간선을 통해 의 유량이 지난다는 뜻이다. 소스에서 나가는 유량이 이고 싱크로 들어오는 유량이 이기 때문에 유량이 7임을 알 수 있다. 싱크로 들어가는 간선의 용량 합이 7이기 때문에 이 값이 최댓값임을 알 수 있다.
최대 유량 문제는 다른 유형의 그래프 문제인 최소 컷(minimum cut) 문제로 연결될 수 있음이 알려져 있다. 최소 컷 문제는 간선 중 일부를 제거하여 소스에서 싱크로 가는 경로를 없애되, 그러면서 제거한 간선의 가중치 합을 최소로 만드는 문제이다.
예를 들어 그림 17의 그래프를 다시 생각해 보자. 이 그래프의 최소 컷은 7인데, 그림 19에 나온 것과 같이 간선 과 간선 를 제거하면 조건을 만족하기 때문이다. 간선을 제거하고 나면 소스에서 싱크로 가는 경로가 없어진다. 컷의 크기는 이고, 가중치의 합이 7보다 작은 컷이 없기 때문에 이 값은 최소가 된다.
- 그림 17. 소스가 1번 노드이고 싱크가 6번 노드인 그래프
- 그림 18. 그래프의 최대 유량은 7이다.
- 그림 19. 그래프의 최소 컷은 7이다.
예제 그래프에 대한 최대 유량과 최소 컷이 같은 것은 우연이 아니다. 두 값이 항상 일치한다고 알려져 있으며, 두 가지 개념은 동전의 양면과 같다. 이제 그래프의 최대 유량과 최소 컷을 찾는 포드-풀커슨 알고리즘을 살펴볼 것이다. 이 알고리즘을 이해하면 왜 두 값이 같은지 알게 될 것이다.
포드-풀커슨 알고리즘
포드-풀커슨 알고리즘(Ford-Fulkerson algorithm) 은 그래프의 최대 유량을 찾는 알고리즘이다. 유량이 0인 상태에서 알고리즘을 시작하고, 단계마다 소스에서 싱크로 가는 경로 중 유량을 늘릴 수 있는 경로(증강 경로, augmenting path)를 찾는다. 더는 유량을 늘릴 수 없을 때의 값이 최대 유량이 된다.
이 알고리즘에서는 간선마다 반대 방향의 간선도 추가한 형태의 특별한 그래프 표현을 사용한다. 각 간선의 가중치는 유량을 얼마나 늘릴 수 있는지를 나타낸다. 알고리즘의 시작 단계에서는 원래 간선의 가중치를 간선의 용량과 동일하게 두고, 반대 방향 간선의 가중치를 0으로 둔다. 그림 20에 예제 그래프에 대한 표현이 나와 있다.
- 반대 간선은 이미 보낸 유량을 나중에 취소하거나 재조정하기 위해 잔여 그래프에 추가하는 가상 간선
포드-풀커슨 알고리즘은 여러 라운드로 구성되어 있다. 라운드마다 소스에서 싱크로 가는 경로 중 모든 간선의 가중치가 양수인 경로를 찾는다. 그러한 경로가 여러 가지라면 어떤 것을 선택해도 된다. 선택한 경로에 포함된 간선의 가중치 최솟값이 라면 유량을 만큼 증가시킬 수 있다. 이를 위해 경로 상의 각 간선에 대해 그 가중치를 만큼 감소시키고, 반대 방향 간선의 가중치를 만큼 증가시킨다.
- 그림 20. 포드-풀커슨 알고리즘에서 사용하는 그래프 표현
이 알고리즘에서 사용된 아이디어는 간선의 유량이 증가하면 앞으로 추가할 수 있는 유량은 감소한다는 데 바탕을 두고 있다. 알고리즘을 진행하면서 다른 경로를 택하는 것이 더 유리한 상황임을 알게 되었다면, 역으로 반대 방향 간선을 이용하여 기존의 유량을 감소시키는 것도 가능하다. 소스에서 가중치가 양수인 간선을 이용하여 싱크로 가는 경로가 존재하는 동안 이 알고리즘을 계속 반복한다. 만일 그러한 경로가 존재하지 않는다면 최대 유량을 구한 것이며, 알고리즘은 종료한다.
그림 21에 포드-풀커슨 알고리즘을 이용하여 예제 그래프의 최대 유량을 찾는 과정이 나와 있다. 알고리즘은 네 번의 라운드로 진행된다. 첫 번째 라운드에서는 경로 을 선택한다. 이 경로상의 최소 가중치는 2이므로 유량이 2만큼 증가한다. 다음으로 경로를 세 번 더 선택한 뒤, 유량을 각각 3, 1, 1만큼 증가시킨다. 그 다음에는 가중치가 양수인 간선으로 구성된 경로가 없고, 최대 유량은 이 된다.
- 그림 21. 포드-풀커슨 알고리즘
경로 찾기
앞에서 살펴본 포드-풀커슨 알고리즘에서 유량을 증가시키는 경로를 선택하는 기준이 따로 정해져 있지는 않았다. 어떤 방식으로 경로를 고르더라도, 시간의 차이는 있지만 알고리즘은 항상 종료하고 최대 유량을 올바르게 찾는다. 하지만 알고리즘의 효율성은 경로를 어떻게 선택하는지에 크게 영향을 받는다. 경로를 찾는 간단한 방법 하나는 깊이 우선 탐색을 이용하는 것이다. 이 방법은 대부분의 경우에 잘 동작하지만, 최악의 경우에는 경로를 선택할 때마다 유량이 1씩 증가하여 알고리즘이 매우 느려질 수 있다. 다행히도 다음에 소개할 여러 기법 중 하나를 사용하면 이러한 상황을 방지할 수 있다.
에드몬드-카프 알고리즘
에드몬드-카프 알고리즘(Edmonds-Karp algorithm) 에서는 경로를 이루는 간선의 개수가 최소가 되도록 경로를 선택한다. 깊이 우선 탐색 대신 너비 우선 탐색을 이용하면 그러한 경로를 찾을 수 있다. 이 경우 유량이 빠르게 증가한다는 것을 증명할 수 있으며, 알고리즘의 시간 복잡도는 이 된다.
- V : 같은 간선이 병목으로 다시 등장할 수 있는 최대 횟수
- E : 병목 후보 간선 개수
- E : 매번 BFS로 증강 경로를 찾는 비용
while BFS로 S→T 경로를 찾을 수 있으면:
그 경로의 병목 용량을 구한다.
그만큼 유량을 보낸다.1. 잔여 그래프를 만든다.
2. BFS로 source → sink까지 갈 수 있는 가장 짧은 증강 경로를 찾는다.
3. 그 경로에서 보낼 수 있는 최대 유량 amount를 구한다.
4. 정방향 간선 cap은 줄이고, 역방향 간선 cap은 늘린다.
5. 더 이상 sink까지 갈 수 없으면 종료한다.#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4e18;
struct Edge {
int to; // 도착 정점
int rev; // 반대 방향 간선의 위치
ll cap; // 현재 남은 용량, 즉 잔여 용량
};
class EdmondsKarp {
private:
int n;
vector<vector<Edge>> graph;
// 현재 잔여 그래프에서, 간선 수가 가장 적은 증강 경로(유량을 보낼 수 있는 경로)를 찾기
bool bfs(
int source,
int sink,
vector<int>& parentNode,
vector<int>& parentEdge
) {
fill(parentNode.begin(), parentNode.end(), -1);
fill(parentEdge.begin(), parentEdge.end(), -1);
queue<int> q;
q.push(source);
parentNode[source] = source;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int i = 0; i < (int)graph[cur].size(); i++) {
Edge& e = graph[cur][i];
// 잔여 용량이 없는 간선은 사용할 수 없음 || 이미 방문한 정점은 다시 방문하지 않음
if (e.cap <= 0 || parentNode[e.to] != -1) continue;
parentNode[e.to] = cur;
parentEdge[e.to] = i;
if (e.to == sink) {
return true;
}
q.push(e.to);
}
}
return false;
}
public:
EdmondsKarp(int n) : n(n), graph(n) {}
void addEdge(int from, int to, ll cap) {
// {from, to: 반대 간선의 위치, cap}
Edge forward = {to, (int)graph[to].size(), cap};
Edge backward = {from, (int)graph[from].size(), 0};
graph[from].push_back(forward);
graph[to].push_back(backward);
}
ll maxFlow(int source, int sink) {
if (source == sink) return 0;
ll totalFlow = 0;
vector<int> parentNode(n);
vector<int> parentEdge(n);
while (bfs(source, sink, parentNode, parentEdge)) {
// 증강 경로 위의 최소 잔여 용량 찾기
ll amount = INF;
for (int v = sink; v != source; v = parentNode[v]) {
int u = parentNode[v];
int edgeIndex = parentEdge[v];
amount = min(amount, graph[u][edgeIndex].cap);
}
// 경로 위의 정방향 간선은 감소,
// 역방향 간선은 증가
for (int v = sink; v != source; v = parentNode[v]) {
int u = parentNode[v];
int edgeIndex = parentEdge[v];
Edge& e = graph[u][edgeIndex];
e.cap -= amount;
graph[e.to][e.rev].cap += amount;
}
totalFlow += amount;
}
return totalFlow;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
EdmondsKarp ek(n);
for (int i = 0; i < m; i++) {
int from, to;
ll cap;
cin >> from >> to >> cap;
from--;
to--;
ek.addEdge(from, to, cap);
}
int source, sink;
cin >> source >> sink;
source--;
sink--;
cout << ek.maxFlow(source, sink) << '\n';
return 0;
}용량 조절 알고리즘
용량 조절 알고리즘(capacity scaling algorithm)1 에서는 깊이 우선 탐색을 이용하여 경로를 찾는데, 이때 각 간선의 가중치가 지정된 값 이상이어야 한다. 처음에는 기준값을 적당히 큰 값으로 설정하며, 예를 들면 그래프의 모든 간선의 가중치 합으로 설정할 수 있다. 경로를 찾을 수 없는 경우 기준값을 2로 나눈다. 기준값이 0이 되면 알고리즘을 종료한다. 이 알고리즘의 시간 복잡도는 로, 이때 는 초기 기준값이다.
실제로는 경로를 찾을 때 깊이 우선 탐색을 사용할 수 있는 용량 조절 알고리즘이 더 구현하기 쉽다. 두 알고리즘 모두 대회에 나오는 문제를 충분히 풀 수 있을 만큼 효율적이다.
디닉 알고리즘
디닉 알고리즘(Dinic algorithm) 도 있다.
- 실전 최대유량 기본 알고리즘
- [Algo] 유량 네트워크 (4) 디닉 알고리즘(Dinic’s Algorithm)
while BFS로 레벨 그래프를 만들 수 있으면:
while DFS로 레벨 그래프 안에서 유량을 보낼 수 있으면:
가능한 만큼 유량을 보낸다.최소 컷
포드-풀커슨 알고리즘을 이용하여 최대 유량을 찾았다면, 그 결과에서 최소 컷을 바로 찾을 수 있다. 알고리즘을 실행한 이후의 그래프에 대해, 를 소스에서 가중치가 양수인 간선을 이용하여 갈 수 있는 노드의 집합(잔여 그래프, residual graph)으로 정의하자. 최소 컷은 원래 그래프에서 에 속한 노드에서 에 속하지 않은 노드로 가는 간선으로 구성되며, 그러한 간선의 용량은 최대 유량을 구할 때 모두 사용되었다. 그림 22를 예로 들면 는 1, 2, 4번 노드로 구성되고, 최소 컷에 속하는 간선은 , 로 가중치의 합은 이다.
- 그림 22. 1, 2, 4번 노드가 집합 에 속한다.
알고리즘을 수행하여 찾은 유량이 최대이고 컷이 최소인 이유는 무엇일까? 그 이유는 그래프의 유량이 컷보다 클 수 없기 때문이다. 따라서 유량과 컷의 값이 같다면, 각각은 최대 유량과 최소 컷이 된다.
위의 성질이 왜 성립하는지를 알아보기 위해 다음과 같은 컷을 생각해 보자. 그래프의 노드를 두 집합으로 나누는데, 소스는 에, 싱크는 에 속하고, 두 집합의 노드를 잇는 간선은 컷이 된다(그림 23). 컷의 크기는 에서 로 가는 간선의 가중치 합이다. 이 값은 그래프의 유량의 상한이 되는데, 이는 흐름의 방향이 에서 로 가는 방향이기 때문이다. 즉, 최대 유량의 크기는 그래프의 어떤 컷의 크기보다도 항상 작거나 같다. 한편, 포드-풀커슨 알고리즘의 결과로 얻은 최대 유량은 그래프의 컷의 크기와 일치한다. 그러므로 이 결과는 최대 유량이면서 최소 컷이 된다.
- 그림 23. 와 사이의 간선
연습문제
Footnotes
-
이 아름다운 알고리즘은 잘 알려지지 않았다. 자세한 설명은 아후자(Ahuja), 매그난티(Magnanti), 올린(Orlin)의 교과서에서 찾을 수 있다. - Network Flows: Theory, Algorithms, and Applications, (Pearson, 1993) ↩