[백준/BOJ C++] 최대 유량 최소 컷 정리 (Max-Flow Min-Cut Algorithm, MFMC)

이 포스트에서는 알고리즘의 일종인 '최대 유량 최소 컷 정리'에 대해 다루고 있습니다.

 

알고리즘에 대한 적절한 적용 상황을 제시하기 위해 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 14286번 : '간선 끊어가기 2' 문제의 풀이 코드와 해설을 함께 다룹니다.

 

 

최대 유량 최소 컷 정리

컷이란 그래프의 노드들을 두 개의 덩어리로 나누는 것을 의미합니다. (무향 그래프에서는 두 그룹 사이에 어떠한 간선도 존재하지 않아야 하지만, 유향 그래프의 경우에는 Sink에서 Sour로 이동이 가능해도 Sour에서 Sink로 이동이 불가능하기만 하다면 역시 컷에 해당합니다.)

이 때, 그래프를 나누기 위해 간선을 끊으면서 그 간선의 비용을 계산한다고 할 때, 컷(그래프를 두 개로 나누는 과정)의 비용이 최소가 되도록 자르는 것을 최소 컷이라고 합니다.

 

그런데 이 문제를 잘 생각해보면 Min-Cut의 비용은 두 그래프의 사이에 흐를 수 있는 최대 유량과 같습니다.

최대 유량 최소 컷 정리란, 최대 유량의 양과 최소 컷의 비용이 동일함을 활용하는 정리입니다.

 

정리 : Flow(유량) <= Max Flow(최대 유량) = Min Cut(최소 컷) <= Cut(컷)

 

 

MFMC 활용

이를 활용하는 대표적인 방법은, 최대 유량 알고리즘을 이용하여 최소 컷 정리를 푸는 것입니다.

 

어떤 그래프에서 최대 유량을 흘려줄 때 유량이 더 흐를 수 있는 간선과 노드들을 하나의 덩어리로, 그리고 나머지 노드들을 나머지 덩어리로 보면 두 개의 노드 덩어리로 분리가 됨을 확인할 수 있습니다.

 

간선 (A, B)에서 A까지는 추가 유량이 도달할 수 있는데 B로는 추가 유량이 도달하지 않는 경우 간선 (A, B)가 Min Cut에서 끊어지는 간선에 해당합니다.

 

 

14286번 : 간선 끊어가기 2

14286번: 간선 끊어가기 2

 

이 문제는 최대 유량 최소 컷 정리를 그대로 사용하라고 지시하는 정석적인 예제입니다.

하나의 그래프를 두 개의 비연결 그래프로 만들 수 있는 최소 컷의 값을 물어보고 있습니다.

 

우리는 최소 컷이 최대 유량과 같음을 알고 있으므로, 이 문제를 풀기 위해 그래프를 해석할 필요 없이 그저 최대 유량만 그대로 구해주면 됩니다.

 

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 505
#define INF 1000000000
using namespace std;

int Capacity[MAX][MAX], Flow[MAX][MAX];
vector<int> Line[MAX];

void AddLine(int From, int To, int Cap) {
    Line[From].push_back(To), Line[To].push_back(From);
    Capacity[From][To] = Capacity[To][From] = Cap;
}

int MaxFlow(int Sour, int Sink) {
    int FlowSum = 0;
    while(true) {
        int Parent[MAX] = {};
        queue<int> Queue;
        Queue.push(Sour);
        Parent[Sour] = Sour;
        while(!Queue.empty() && !Parent[Sink]) {
            int Cur = Queue.front();
            Queue.pop();
            for(int i=0; i<Line[Cur].size(); i++) {
                int Next = Line[Cur][i];
                if(Capacity[Cur][Next] - Flow[Cur][Next] > 0 && !Parent[Next]) {
                    Queue.push(Next);
                    Parent[Next] = Cur;
                    if(Next == Sink) break;
                }
            }
        }
        if(!Parent[Sink]) break;

        int Amount = INF;
        for(int i=Sink; i!=Sour; i=Parent[i])
            Amount = min(Amount, Capacity[Parent[i]][i] - Flow[Parent[i]][i]);
        for(int i=Sink; i!=Sour; i=Parent[i]) {
            Flow[Parent[i]][i] += Amount;
            Flow[i][Parent[i]] -= Amount;
        }
        FlowSum += Amount;
    }
    return FlowSum;
}

int main() {
    int N, M, From, To, Cap, Sour, Sink;
    scanf("%d %d", &N, &M);
    for(int i=0; i<M; i++) {
        scanf("%d %d %d", &From, &To, &Cap);
        AddLine(From, To, Cap);
    }
    scanf("%d %d", &Sour, &Sink);
    printf("%d", MaxFlow(Sour, Sink));
}

 

최대 유량 알고리즘은 이전에 다루었기 때문에 코드에 대해 길게 설명하지는 않겠습니다.

 

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

 

최대 유량 알고리즘은 위의 링크에 정리되어 있으니 참고하시면 유용할 것입니다.

어쨌든 주어진 그래프를 연결하고, 최대 유량을 계산해준 뒤 출력해주면 됩니다.

주의할 점은, 이 그래프는 방향이 없는 무향 그래프라고 하였으므로, Capacity를 설정할 때 A → B로 설정하는 것뿐만이 아니라 B → A로도 Capacity를 설정해주어야 합니다. (Capacity[From][To] = Capacity[To][From] = Cap)

 

 

 

알고리즘 자체가 원리만 이해한다면 실제로는 공부할 것이 아무것도 없는, 재미있는 정리였습니다.

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