[C++ 알고리즘] 최대 유량 알고리즘 (Network Flow, Ford-Fulkerson, Edmonds-Karp)

이 포스트에서는 최대 유량 알고리즘(Network Flow, Ford-Fulkerson, Edmonds-Karp 알고리즘)에 대한 설명과 코드 구현에 대해 다룹니다.

 

알고리즘에 대한 적절한 예시를 들기 위해, 프로그래밍 문제 사이트 백준 Online Judge의 6086번 : '최대 유량' 문제를 풀이하면서 설명하도록 하겠습니다.

 

 

6086번 : 최대 유량

6086번: 최대 유량

 

특정 지점부터 특정 지점까지 흐를 수 있는 다양한 지점들 사이의 최대 유량이 주어졌을 때, A 지점부터 Z 지점까지 흐를 수 있는 최대 유량을 구하는 문제입니다.

 

이렇게 그래프의 노드들 사이의 유량이 주어졌을 때 두 지점 사이의 최대 유량을 구하는 알고리즘을 최대 유량 알고리즘(또는 Network Flow, Ford-Fulkerson, Edmonds-Karp 알고리즘)이라고 합니다.

 

풀이를 먼저 코드로 구현하고, 이에 대해 설명해보도록 하겠습니다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> adj, cap, flo;

int f(char c) {
    if(c >= 'A' && c <= 'Z') return c - 'A' + 1;
    else if(c >= 'a' && c <= 'z') return c - 'a' + 27;
}

int flow(int sour, int dest) {
    int sum = 0;

    while(true) {
        vector<int> p(60, -1);

        queue<int> q;
        q.push(sour);

        while(!q.empty() && p[dest] == -1) {
            int x = q.front();
            q.pop();

            for(int i=0; i<adj[x].size(); i++) {
                int y = adj[x][i];

                if(cap[x][y] - flo[x][y] <= 0 || p[y] != -1) continue;

                p[y] = x;
                q.push(y);

                if(y == dest) break;
            }
        }
        if(p[dest] == -1) break;

        int val = INT_MAX;

        for(int i=dest; i!=sour; i=p[i])
            val = min(val, cap[p[i]][i] - flo[p[i]][i]);

        for(int i=dest; i!=sour; i=p[i]) {
            flo[p[i]][i] += val;
            flo[i][p[i]] -= val;
        }

        sum += val;
    }

    return sum;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    adj.resize(60);
    cap.resize(60, vector<int>(60));

    while(N--) {
        char a, b; int c; cin >> a >> b >> c;

        adj[f(a)].push_back(f(b));
        adj[f(b)].push_back(f(a));

        cap[f(a)][f(b)] += c;
        cap[f(b)][f(a)] += c;
    }

    flo.resize(60, vector<int>(60));

    cout << flow(f('A'), f('Z')) << "\n";
}

 

 

먼저 선언된 변수들의 정의에 대해 설명하겠습니다.

Capacity[A][B]는 A에서 B로 흐를 수 있는 최대 유량을, Flow[A][B]는 A에서 B로 흐르는 현재 유량(계산 과정에서 기록하기 위해)을 의미합니다.

Line[A][i] = B는 A와 B가 간선으로 연결되어 있음을 의미합니다.

Sour는 출발지를, Sink는 목적지를 의미합니다. (탐색 중에는 이 두 값이 그래프 전체의 시작점과 도착점이 아닌, 임시적으로 지정한 시작점과 도착점을 의미합니다.)

Parent[A]는 A번 노드로 도달하기 전의 노드인, A번 노드를 가리키고 있는 이전 노드를 의미합니다. (이 변수를 선언한 이유는 문제에서 양방향 그래프를 제시했고, 무엇보다도 탐색 과정에서 경로를 역으로 거슬러 가기 쉽도록 구현하기 위해서입니다.)

 

이제 MaxFlow 함수에 대해 설명하겠습니다. (여기가 최대 유량 알고리즘)

먼저 BFS로 Sour에서부터 탐색을 시작하면서, "유체가 더 흘러서" Sour에서 Sink까지 도달할 수 있는 경로를 찾고 이 때 지나간 노드들의 Parent를 기록해줍니다. (19행 ~ 34행)

그러다가 경로를 찾으면, Sink에서 아까 탐색하면서 도달한 노드들을 역으로 거슬러 올라가면서 흐를 수 있는 유체의 양(= 지나온 경로 중에서 가장 작은 Capacity)을 찾아 그만큼의 유체가 흘렀음을 기록해줍니다.

이 때 중요한 점은 역방향으로 흐른 유체는 마이너스로 기록을 해줍니다. (예를 들어 A에서 B로 5의 유량이 흘렀으면, 이것은 B에서 A로 -5의 유량이 흐른 것과 같으므로 역시 기록해줍니다. 그래야 특정 경로의 유량을 줄여서 새로운 경로를 통해 최대 유량을 늘릴 수 있는 경우, 해당 경로를 찾아줄 수 있습니다.)

마지막으로 구한 Amount만큼 Sum에 합해줍니다.

 

이 과정을 가능한 모든 루트를 찾아서 기록해주면, Sum이 최대 유량이 되는 것입니다.

 

 

 

풀이 코드대로 알고리즘을 짜서 제출해보면, 위와 같이 정답 처리를 받을 수 있습니다.

이 문제에서는 노드와 간선 수의 제한이 작기 때문에, 거의 0ms에 수렴하는 시간으로 통과가 가능합니다.

 

다음 포스트부터는 최대 유량 알고리즘을 활용한 문제들을 풀이해보겠습니다.