[알고리즘] 네트워크 유량, 포드-폴커슨(Ford-Fulkerson) 알고리즘 (Java)

Dot Algo∙ DS/알고리즘 개념

[알고리즘] 네트워크 유량, 포드-폴커슨(Ford-Fulkerson) 알고리즘 (Java)

루지 2021. 12. 27. 15:43

네트워크 유량

그래프 문제에는 경로의 길이 외에도 그래프에 대해 정의할 수 있는 중요한 개념이 있다. 바로 그래프의 ‘용량’이다. 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 ‘흐름’ 혹은 ‘유량’을 보낼 수 있는지를 계산하는 문제를 네트워크 유량(network flow) 문제라고 부른다.

교통망에서 두 도시 사이를 이동할 수 있는 시간당 차량의 수, 송유관 네트워크에서 두 도시 사이에 보낼 수 있는 석유의 양 등 네트워크 유량은 현실에서 자주 찾을 수 있는 문제들이다.
또한 네트워크 유량은 굉장히 강력한 최적화 문제로, 그래프와 별 상관이 없어 보이는 다양한 최적화 문제들을 푸는 데도 이용할 수 있다.

유량 네트워크(flow network)란 각 간선에 용량(capacity)이라는 추가 속성이 존재하는 방향 그래프를 뜻한다.

이때 각 간선은 유량을 흘려보낼 수 있는 파이프 역할을 한다.

네트워크의 유량이 가지는 세 가지 속성

정점 u에서 v로 가는 간선의 용량을 c(u,v), 실제 흐르는 유량을 f(u,v)라고 쓸 때, 네트워크 유량은 다음 세 가지 속성을 만족해야 한다.

용량 제한 속성 f(u,v) ≤ c(u,v)

가장 자명한 속성으로, 각 간선의 유량은 해당 간선의 용량을 초과할 수 없다.

유량의 대칭성 f(u,v) = -f(u,v)

u에서 v로 유량이 흘러올 경우, v의 입장에서는 u로 음수의 유량을 보내는 것이다

유량의 보존 Σf(u,v) = 0

이 속성은 각 정점에 들어오는 유량과 나가는 유량의 양은 정확히 같아야 함을 나타낸다. 유량의 대칭성에 의해 정점에 들어오는 유량은 모두 음수로 표현되므로, 한 정점에서 다른 모든 정점에 보내는 유량을 합하면 항상 0이 되어야한다.

소스(source)와 싱크(sink)

유량 네트워크에는 항상 특수한 두 정점 소스(source)와 싱크(sink)가 존재한다.

소스는 유량이 시작되는 정점이고,
싱크는 유량이 도착하는 정점이다.
따라서 이 두 정점에서는 유량의 보존 속성은 성립하지 않는다. 하지만 다른 모든 정점에 유량의 보존 속성이 성립해야 하기 때문에, 소스에서 나온 모든 유량은 결국 싱크로 들어가게 된다.

네트워크 유량 문제는 이렇게 소스와 싱크 사이에 흐를 수 있는 최대 유량을 계산하는 문제이다. 그리고 이 네트워크 유량 문제를 해결하는 가장 간단한 알고리즘으로 포드-폴커슨 알고리즘이 있다.

포드-폴커슨 알고리즘

네트워크 유량 문제를 해결하는 가장 기초적인 방법으로 포드-폴커슨 알고리즘(Ford-Fulkerson algorithm)이 있다. 포드-폴커슨 알고리즘은 최초로 고안된 네트워크 유량 알고리즘으로 개념과 구현이 비교적 간단하다. 이보다 빠른 알고리즘도 여럿 존재하지만 프로그래밍 대회에 출제되는 규모의 문제를 풀 때 큰 문제가 없으므로 대부분 이 방법을 사용한다.

동작 원리

포드-폴커슨 알고리즘의 동작 원리는 아주 간단하다.

유량 네트워크의 모든 간선의 유량을 0으로 두고 시작해,
소스에서 싱크로 유량을 더 보낼 수 있는 경로를 찾아 유량을 보내기를 반복한다.

증가 경로(argumenting path)

(a)는 모든 간선의 유량이 0인 텅 빈 네트워크를 보여준다. s가 소스, t가 싱크라고 할 때 굵은 점선으로 표시된 경로를 이용하면 s에서 t로 1만큼의 추가 유량을 보낼 수 있다.

(b)에서 한번 더 굵은 점선으로 표시된 경로를 이용하면 1의 추가 유량을 t로 보내 (c)와 같은 상태를 얻을 수 있다. 이렇게 유량을 보내는 경로를 증가 경로(argumenting path)라고 부른다.

잔여 용량(residual capacity)

경로를 따라 유량을 보낼 수 있으려면 각 간선에 이미 흐르고 있는 유량 외에 추가로 유량을 보낼 수 있는 여유 용량이 있어야 한다. 예로, 용량이 10인 간선에 이미 4만큼의 유량이 흐르고 있다면 이제 더 흘려보낼 수 있는 유량의 양은 6이고 이를 잔여 용량(residual capacity)이라고 부른다.

잔여 용량(residual capacity) = 간선의 용량 - 유량
r(u, v) = c(u, v) - f(u, v)

이때 증가 경로를 통해 흘려보낼 수 있는 유량의 최대량은, 포함된 간선의 잔여 용량 중 가장 작은 값으로 결졍된다. (a)에서 (a, t)로는 2의 유량을 더 보낼 수 있지만, (s, a)로는 1의 유량 밖에 보낼 수 없으므로 경로 s-a-t를 통해서는 최대 1의 유량만 보낼 수 있다.

포드-폴커슨 알고리즘은 이와 같은 증가 경로가 더이상 존재하지 않을 때까지 증가 경로를 찾고, 보낼 수 있는 최대 유량을 해당 경로를 따라 보내는 작업을 반복한다. 그런데 아직 풀어야 할 문제가 있는데 바로 경로 선택 방식이다.

어떤 증가 경로를 선택해야 최대 유량을 찾을 수 있을까?

(a)의 네트워크에서 증가 경로를 찾는데 s-a-t 대신 s-a-b-t가 찾아졌다고 하자. 이대로 유량을 보내면 다음과 같은 상태를 얻을 수 있는데, 이제는 더이상 s에서 t로 유량을 보낼수 가 없게 된다.

유량이 가지는 속성 중 하나인 대칭성을 돌이켜보면 이 문제를 해결할 수 있다.

b에서 a로 가는 간선은 없으므로 해당 간선의 용량은 c(b, a)는 0이다.
유량의 대칭성에 의하면 유량 f(b, a) = -1 이다.
앞선 식에 따라 잔여 용량을 계산하면 r(b, a) = c(b, a) - f(b, a) = 1 임을 알 수 있다.

그러면 도출해낸 결과로는 b에서 a로 1만큼의 유량을 보낼 수 있다는 소리인데 어떻게 실제로 존재하지도 않는 간선으로 유량을 보낼 수 있다는 것일까?

이쪽으로 흘러오는 유량을 줄이는 것은 상대에게 유량을 보내주는 것과 같은 효과를 갖기 때문이다.
(b,a)로 흐르게 함으로써 (s,b)로 흐를 수 있는 유량이 그만큼 증가한다는 뜻이다.

이와 같은 속성은 두 정점이 서로 상대에게 유량을 보내 주는 것은 의미가 없기 때문에 성립한다. 그럼 이제 새로운 그래프를 다시 보자.

포드-폴커슨 알고리즘 구현 및 시뮬레이션

백준 6086번 최대 유량을 통해 포드-폴커슨 알고리즘을 구현해보자. 이론을 이해했다면 구현은 간단하다. 잔여 용량이 남은 간선들만을 사용하는 BFS 탐색을 이용하여 증가 경로를 찾고, 이를 따라 유량을 보내는 일을 더이상 증가경로가 없을 때 까지 반복하면 된다.

capacity[][] : 각 간선의 용량
flow[][]: 간선을 따라 흐르는 유량
잔여용량 = capacity[][] - flow[][]
src: 출발점, sink: 도착점

시뮬레이션

흐름을 더 잘 이해하기 위해 주어진 예제와는 값이 좀 다르게 변형해서 시뮬레이션을 돌려보자. 유량의 초기 상태는 다음과 같다.

1. src = A를 시작으로 잔여 용량이 남아있는 간선을 BFS를 통해 탐색한다.

A-B 잔여용량 = 6-0 = 6
B-Z 잔여용량 = 3-0 = 3
B-C 잔여용량 = 3-0 = 3
Z에 도달한 간선이 있으므로 BFS 탐색 종료

2. 1번에서 탐색한 정보를 통해 증가 경로를 통해 유량을 얼마나 보낼지 결정한 후 유량을 내보낸다.

B-Z의 최대 유량은 3, A-B의 최대 유량은 6 이므로 유량은 3이다.
구한 유량의 양을 그대로 src(A)에서 sink(Z)로 내보낸다. 단, 여기서 대칭성을 고려하여 반대 유량도 고려해줘야 한다.
- flow[A][B] = 3, flow[B][A] = -3
- flow[B][Z] = 3, flow[Z][B] = -3

3. 새롭게 다시 다른 잔여용량이 남아있는지 BFS를 통해 탐색한다.

A-B 잔여용량 = 6-3 = 3
B-C 잔여용량 = 3-0 = 3
C-D 잔여용량 = 5-0 = 5
D-Z 잔여용량 = 4-0 = 4
Z에 도달한 간선이 있으므로 BFS 탐색 종료

4. 2번과 마찬가지로 증가 경로를 통해 보낼 유량의 크기를 구하여 보내준다.

3번에서 구한 잔여 용량의 최소는 3이므로 최대로 보낼 수 있는 유량은 3이다.
구한 유량의 양을 그대로 src(A)에서 sink(Z)로 내보낸다. 단, 여기서 대칭성을 고려하여 반대 유량도 고려해줘야 한다.

전체 코드

import java.io.*;
import java.util.*;

public class Main {

	static int INF = 987654321, V = 52;
	static int[][] flow, capacity;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		flow = new int[V][V];
		capacity = new int[V][V];
		StringTokenizer st;
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int a = atoi(st.nextToken().charAt(0));
			int b = atoi(st.nextToken().charAt(0));
			int cost = Integer.parseInt(st.nextToken());
			
			capacity[a][b] += cost;
			capacity[b][a] += cost;
		}
		
		maxFlow(0,25);
	}
	
	static void maxFlow(int src, int sink) {
		int totalFlow = 0;
		int[] parent = new int[V];
		Queue<Integer> q;
		while(true) {
			Arrays.fill(parent, -1);
			q = new LinkedList<>();
			
			parent[src] = src;
			q.add(src);
			
			while(!q.isEmpty() && parent[sink] == -1) {
				int cur = q.poll();
				for(int nxt =0; nxt<V; nxt++) {
					// 잔여 용량이 남아 있는 간선을 따라 탐색한다. 
					if(capacity[cur][nxt] - flow[cur][nxt] > 0 && parent[nxt] == -1) {
						q.add(nxt);
						parent[nxt] = cur;
					}
				}
			}
			
			// 더이상 증가 경로가 없으면 종료 
			if(parent[sink] == -1) break;
			
			// 증가 경로를 통해 유량을 얼마나 보낼지 결정한다. 
			int amount = Integer.MAX_VALUE;
			for(int i=sink; i!=src; i=parent[i]) {
				amount = Math.min(capacity[parent[i]][i] - flow[parent[i]][i], amount);
			}
			
			// 증가 경로를 통해 유량을 보낸다. 
			for(int i=sink; i!=src; i=parent[i]) {
				flow[parent[i]][i] += amount;
				flow[i][parent[i]] -= amount;
			}
			
			totalFlow += amount;
			
		}
		System.out.println(totalFlow);
	}
	
	static int atoi(char c) {
		if('A' <= c && c <= 'Z') {
			return c-'A';
		}else if('a' <= c && c <= 'z'){
			return c-'A'-6;
		}
		return -1;
	}
}