[알고리즘 정리]네트워크 플로우(Network Flow) 알고리즘_에드몬드 카프 알고리즘(Edmonds-Karp algorithm)

네트워크 플로우

 

 코드적으로 이해하는것이 조금 어려울 수 있지만, 개념자체는 간단하게 "도착지(Sink)에 얼마나 물이 나오게 할 수 있느냐?"에 관한 문제입니다.

그림을 보면 쉽게 이해 할 수 있다.

위의 문제에서 각 Source와 각 수도관은 주어진 리터만큼 시간당 물을 보낼 수 있고 하였을때,

 Sink에는 시간당 얼만큼의 물이 도달 할 수있냐?

딱, 봐도 8L의 물이 도달 할 수 있다는 것을 알 수 있다.

이 문제를 해결 하는 것이 네트워크 플로우다.

용어 정리 & 주요 특징

- (용어 1) Source : 네트위크(물)의 시작점

- (용어 2) Sink: 네트워크(물)의 도착지점

- (용어 3) c(a,b) : a->b로 흐를 수 있는 물의 최대량(용량) 

- (용어 4) f(a,b) : a->b로 현재 흐르고 있는 물의 양(유량)

- (특징1) 잔여 용량 : c(a,b) - f(a,b)  // a->b로 물을 보낼 수 있는 잔여량(잔여 용량) 

ex) 한 관에 5L를 최대 보낼 수 있는데 현재 3L를 보내고 있다면 당연히 2L를 추가로 보낼 수 있겠다!

- (특징2) 용량 제한 : f(a,b) <= c(a,b) // 당연히 최대 용량 보다는 작거나 같은 물을 보낼 수 있다.

- (특징3) 유량 대칭 : f(a,b) == -f(b,a) // 네트워크 플로우에 가장 중요한 개념 인 것 같다. 

유량 대칭

가장 이해하기 어려웠던 부분이고 이렇게 생각해보니까 쉬웠다.

A, B라는 사람이 c, d에 투자를 하려고한다.

각자 5, 7만원을 가지고 있다.

이때, 먼저 A사람이 d회사에 5만월을 투자하였다. (a->b경로를 이용하여)

여기서 빨간부분 유량대칭과 잔여 용량을 주목하자.

b->a 경로를 통해서 10만원을 투자가 가능하게 되었다!!!

-> 이는 A가 투자했던 5만원을 대신 투자하고 추가로 5만원을 b->a 경로를 통해 투자한다는 의미이다.

이제 다음 B가 7만원을 투자 하려고 한다.

1. A가 투자했던 d회사의 5만원을 본인이 대신 투자한다.

2. A가 투자하였던 5만원과 본인의 투자하고 남은 2만원을 총 7만원을 b->a를 통해 투자하게된다.

3. 7만원을 c회사에 투자하게 된다.

-> 결론적으로 b->a 경로를 통해 B가 2만원을 투자하게 된 것!

문제 도식화

  이제 위에서 본 규칙을 이용해서 문제를 해결 하면된다! 그림을 통해 이해하는 것이 쉬웠던것 같다.

실행 코드

에드몬드 카프 알고리즘(Edmonds-Karp algorithm)알고리즘을 사용하게 되었을때, BFS를 사용하게 된다.

시간 복잡도는 O(VE^2)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 1005
#define INF 987654321
#define MOD 31991
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

int n, c, total = 0, flow[MAX][MAX], capacity[MAX][MAX];

char a, b;
vector<int> v[MAX];
queue<int> q;
bool visit[MAX][MAX];

// 문자 -> 숫자 변환
int f(char ch)
{return ch - 'A';}

int main()
{
	int source = f('A'), sink = f('Z');
	scanf("%d", &n);

	// 입력을 받아온다.
	// 주의 사항 : capacity a-> b를 더해줄때, b->a도 더해줘야 한다.
	for (int i = 0; i < n; i++)
	{
		scanf(" %c %c %d", &a, &b, &c);
		int q = f(a), w = f(b);
		capacity[q][w] += c;
		capacity[w][q] += c;
		v[f(a)].push_back(f(b));
		v[f(b)].push_back(f(a));
	}

	while (1)
	{
		// 경로를 저장
		int prev[MAX];
		fill_n(&prev[0], MAX, -1);

		// 시작지점 추가
		q.push(source);	

		// BFS를 이용하여 경로를 찾는다.
		while (!q.empty())
		{
			int cur = q.front();
			q.pop();
			for (int k = 0; k < v[cur].size(); k++)
			{
				int next = v[cur][k];
				// prev[v[cur][k]] == -1 : next 정점의 방문 여부
				// capacity[cur][next] - flow[cur][next] > 0 : 잔여 용량의 여부
				if (prev[next] == -1 && capacity[cur][next] - flow[cur][next] > 0)
				{
					prev[next] = cur;
					q.push(next);
					if (next == sink)
						break;
				}
			}
		}

		if (prev[sink] == -1)
			break;
		// 더 이상 sink로 가는 경로가 존재하지 않는 경우

		int tmp = sink, possible_flow = INF;
		for (int i = sink ; i != source; i = prev[i])
			possible_flow = min(possible_flow, capacity[prev[i]][i] - flow[prev[i]][i]);
		// 찾은 경로에서의 흐를 수 있는 최소 유량을 확인한다.

		for (int i = sink ; i != source; i = prev[i]) 
		{
			flow[prev[i]][i] += possible_flow;
			flow[i][prev[i]] -= possible_flow;
		}
		// 찾은 경로에 흐를 수 있는 최소 유량을 더해준다.
		// 주의 사항 : 역방향에 대해서도 추가해 줘야한다.(유량 대칭)
		total += possible_flow;
	}
	printf("%d\n", total);
	return 0;
}