[C++ 알고리즘] 최소 비용 최대 유량 알고리즘 (MCMF 알고리즘)

이 포스트에서는 최소 비용 최대 유량 알고리즘(MCMF 알고리즘)에 대한 설명과 알고리즘 구현 코드에 대해 다루고 있습니다.

 

알고리즘에 대한 적절한 예시를 제공하기 위해 프로그래밍 문제 사이트 백준 Online Judge의 11408번 : '열혈강호 5' 문제를 함께 풀이할 것입니다.

 

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

최소 비용 최대 유량(MCMF) 알고리즘은 위의 포스트에 정리된 최대 유량 알고리즘을 사용할 수 있는 상황에, 간선의 비용까지 추가된 조건에서 사용할 수 있는 알고리즘입니다.

 

즉, 간선의 가중치를 거리라고 하였을 때 최단 경로의 최대 유량을 구하는 알고리즘이라고 할 수 있습니다.

 

이러한 상황의 적절한 예시 중 하나를 다음의 예제(BOJ 11408번 : 열혈강호 5)를 풀이하면서 다루어보도록 하겠습니다.

 

 

11408번 : 열혈강호 5

 

문제의 전반적인 형태는 이전에 풀이한 '열혈강호 3', '열혈강호 4' 문제와 상당히 유사합니다.

그러나 이 문제에서는 직원이 일을 할 경우 그 일을 할 때 지불해야하는 월급이 같이 적용되기 때문에 최소 월급으로 할 수 있는 최대 일의 양을 구해야 합니다.

이 경우 기존과 같이 그래프를 구성하되 Dist 배열을 선언하여 다익스트라 알고리즘과 같이 더 짧은 비용으로 도달할 수 있는 구간에 대해서는 비용을 갱신해주면서 풀이를 해주면 됩니다.

 

 

 

풀이를 통해 구성할 그래프를 대략적으로 그려보면 위와 같이 나타낼 수 있습니다.

번호를 매기는 방식은 풀이하는 사람의 생각대로 하면 되겠지만 저의 풀이를 예시로 들면, Sour를 1번 노드로, Sink를 2번 노드로 설정한 뒤 나머지 직원과 일의 번호에 대한 노드를 순차적으로 번호를 매겨줄 수 있습니다.

그 다음 Sour에서 직원 노드 방향으로 연결을 시켜주고 직원 노드에서 일 노드로 연결을, 마지막으로 일 노드에서 Sink 노드로 연결을 시켜줍니다.

이 문제에서는 비용에 대한 개념이 등장하므로 Dist 배열을 선언하여 직원과 일 사이에 입력되는 비용을 추가하여 그 비용이 최소가 나오도록 값을 갱신하는 과정을 반복할 것입니다.

 

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 1000
#define INF 1000000000
#define SOUR 1
#define SINK 2
using namespace std;

int Count = 0, CostSum = 0;
int Capacity[MAX][MAX], Flow[MAX][MAX], SDist[MAX][MAX];
vector<int> Line[MAX];

void MCMF(int Sour, int Sink) {
    while(true) {
        bool isInQueue[MAX] = {};
        int Parent[MAX] = {}, Dist[MAX];
        fill(Dist, Dist+MAX, INF);
        Dist[SOUR] = 0;

        queue<int> Queue;
        Queue.push(Sour);
        isInQueue[Sour] = true;

        while(!Queue.empty()) {
            int Cur = Queue.front();
            Queue.pop();
            isInQueue[Cur] = false;
            for(int i=0; i<Line[Cur].size(); i++) {
                int Next = Line[Cur][i];
                if(Capacity[Cur][Next] - Flow[Cur][Next] > 0
                   && Dist[Cur] + SDist[Cur][Next] < Dist[Next]) {
                    Dist[Next] = Dist[Cur] + SDist[Cur][Next];
                    Parent[Next] = Cur;
                    if(!isInQueue[Next]) {
                        Queue.push(Next);
                        isInQueue[Next] = true;
                    }
                }
            }
        }
        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]) {
            CostSum += Amount*SDist[Parent[i]][i];
            Flow[Parent[i]][i] += Amount;
            Flow[i][Parent[i]] -= Amount;
        }
        Count++;
    }
}

int main() {
    int N, M, W, WNum, D;
    scanf("%d %d", &N, &M);
    for(int i=3; i<3+N; i++) {
        Line[SOUR].push_back(i), Line[i].push_back(SOUR);
        Capacity[SOUR][i] = 1;
        scanf("%d", &W);
        for(int j=0; j<W; j++) {
            scanf("%d %d", &WNum, &D);
            Line[i].push_back(2+N+WNum), Line[2+N+WNum].push_back(i);
            SDist[i][2+N+WNum] = D, SDist[2+N+WNum][i] = -D;
            Capacity[i][2+N+WNum] = 1;
        }
    }
    for(int i=3+N; i<3+N+M; i++) {
        Line[SINK].push_back(i), Line[i].push_back(SINK);
        Capacity[i][SINK] = 1;
    }
    MCMF(SOUR, SINK);
    printf("%d\n%d", Count, CostSum);
}

 

대략적인 풀이 코드는 이전에 풀이했던 열혈강호 3, 4의 코드와 비슷한 구성을 가지도록 구현하였습니다.

SDist[A][B]는 A번 노드에서 B번 노드로 이동하는데 필요한 비용을 의미합니다.

최대 유량 알고리즘에서는 모든 유량의 흐름을 탐색하기 위해 음의 유량을 고려하므로, 비용 역시 반대 방향으로 이동하는 경우 음의 비용을 저장해주어야 합니다. (값이 같이 갱신되어야 하기 때문)

 

MaxFlow 함수에서는 먼저 Dist를 갱신해주기 위해 코드의 구조가 바뀌기 때문에 최적화 된 코드를 위해 isInQueue 배열이 필요해집니다. (이름 그대로 큐에 해당 노드가 저장되어 있는지의 여부를 저장해줍니다.)

Dist 배열은 Source 노드에서 해당 번호의 노드로 이동하는데 필요한 비용을 저장합니다.

이 때 Dist[SOUR] = 0을 제외한 나머지 노드들의 Dist 값은 모두 INF로 설정해줍니다. (다익스트라 알고리즘과 같은 방식임)

이후 탐색 과정은 동일하지만 다음 노드를 방문하기 위한 조건으로 Dist 값을 더 작게 갱신할 수 있는지를 검사합니다.

만약 그렇다면 노드의 Dist 값을 갱신해주고 Parent 값도 갱신해주면서 계속해서 탐색을 해 나갑니다.

 

나머지 유량에 대한 계산 역시도 비슷한데, 여기에서는 Dist(Cost)의 개념이 추가되었으므로 CostSum(문제에서는 지급해야 하는 총 월급)에 유량×Dist 값을 곱해 추가해줍니다.

문제에서 일의 수와 월급의 양을 모두 구하라고 하였으므로 Sour에서 Sink로 가는 경로를 하나 찾아 갱신할 때마다 일의 수 Count를 1 증가시켜줍니다.

 

 

 

제출해보면 위와 같이 정답 처리를 받을 수 있습니다.

 

---

+ 예제로 풀이한 열혈강호 5의 문제와 이어지는 다음의 문제가 있는데, 풀이가 연관된 부분이 워낙 많기 때문에 추가로 이어서 풀이합니다.

 

11409번 : 열혈강호 6

11409번: 열혈강호 6

 

위의 열혈강호 5 문제에서 월급으로 지불해야 할 최소 비용이 아닌, 최대 비용을 구하는 문제입니다.

(문제 사진을 생략한 이유는 최대 최소를 제외하고 나머지 부분은 열혈강호 5 문제와 완전히 동일하기 때문입니다.)

 

처음에는 알고리즘 자체가 최소 비용이 아닌 최대 비용이기 때문에 MCMF 알고리즘을 쓰는 것이 아니라 코드를 다시 짜야하나 생각했는데, 최대 유량 알고리즘 자체가 음의 유량까지 이미 고려된 알고리즘이므로 이를 활용할 수 있었습니다.

즉, Dist 값을 음수로 입력받아 알고리즘을 돌린 뒤 나온 Max Cost 값에 다시 마이너스만 붙여서 출력해주면 되는 문제였습니다.

 

따라서 다음의 두 줄의 코드만 부호만 바뀌도록 수정해주면 됩니다.

수정 1 : SDist[i][2+N+WNum] = -D, SDist[2+N+WNum][i] = D;

수정 2 : printf("%d\n%d", Count, -CostSum);

 

 

 

제출해보면 역시 정답 처리를 받을 수 있습니다.