[백준/BOJ C++] 9413번 : 제주도 관광 (최소 비용 최대 유량)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 9413번 : '제주도 관광' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum III에 해당하며, 문제를 풀이하기 위해 최소 비용 최대 유량(MCMF) 알고리즘에 대한 이해가 필요합니다.

 

 

9413번 : 제주도 관광

 

두 그룹이 주어진 입력대로 연결된 교차로들을 지나며 교차로가 겹치지 않게 동선을 짜려고 할 때, 두 동선의 교차로 수의 합의 최대치를 구하는 문제입니다.

 

 

 

우선 각 intersection들은 노드에 해당하기 때문에 노드를 방문하는 조건이 붙은 문제는 노드를 두 개로 분할하여 그 사이에 용량이 1인 간선을 추가함으로써 해결이 가능합니다.

 

그리고 두 팀이 출발한다고 하였기 때문에 출발지 노드를 하나 더 만들어서 Sour와 출발지 노드 사이에 용량이 2인 간선을 만들어주면 이것 역시 해결이 가능합니다.

 

마지막 아이디어는 방문 가능한 교차로의 최댓값을 구하는 것인데 이것은 분할된 노드 사이의 Cost를 -1로 만들어 이것이 최소가 되게 하고, 구한 답에 마이너스를 붙여 답을 얻을 수 있습니다.

MCMF 알고리즘을 사용할 때 최소가 아닌 최댓값을 구해야 한다면, 이렇게 비용을 마이너스로 붙여 계산한 뒤 얻어지는 결과에 다시 마이너스를 붙임으로써 해결이 가능합니다.

 

↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

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

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

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

int MCMF(int Sour, int Sink) {
    int CostSum = 0;
    while(true) {
        int Prev[MAX], Cost[MAX];
        fill(Prev, Prev+MAX, -1);
        fill(Cost, Cost+MAX, INF);
        Cost[Sour] = 0;

        queue<int> Queue;
        Queue.push(Sour);

        bool isInQueue[MAX];
        fill(isInQueue, isInQueue+MAX, false);
        isInQueue[Sour] = true;

        while(!Queue.empty()) {
            int Curr = Queue.front();
            Queue.pop();
            isInQueue[Curr] = false;
            for(int i=0; i<Line[Curr].size(); i++) {
                int Next = Line[Curr][i];
                if(Capacity[Curr][Next] - Flow[Curr][Next] > 0
                   && Cost[Curr] + SinCost[Curr][Next] < Cost[Next]) {
                    Cost[Next] = Cost[Curr] + SinCost[Curr][Next];
                    Prev[Next] = Curr;
                    if(!isInQueue[Next]) {
                        Queue.push(Next);
                        isInQueue[Next] = true;
                    }
                }
            }
        }
        if(Prev[Sink] == -1) break;

        int Amount = INF;
        for(int i=Sink; i!=Sour; i=Prev[i])
            Amount = min(Amount, Capacity[Prev[i]][i] - Flow[Prev[i]][i]);
        for(int i=Sink; i!=Sour; i=Prev[i]) {
            CostSum += Amount*SinCost[Prev[i]][i];
            Flow[Prev[i]][i] += Amount;
            Flow[i][Prev[i]] -= Amount;
        }
    }
    return CostSum;
}

int main() {
    int T, N, M, Start, Sour, Sink, From, To;
    scanf("%d", &T);
    for(int t=0; t<T; t++) {
        fill(&Capacity[0][0], &Capacity[MAX-1][MAX], 0);
        fill(&Flow[0][0], &Flow[MAX-1][MAX], 0);
        fill(&SinCost[0][0], &SinCost[MAX-1][MAX], INF);
        for(int i=0; i<MAX; i++) vector<int>().swap(Line[i]);

        scanf("%d %d", &N, &M);
        Start = 2*N+1, Sour = 2*N+2, Sink = 2*N+3;
        AddLine(Sour, Start, 2, 0);
        for(int i=1; i<=N; i++) {
            AddLine(Start, i, 1, 0);
            AddLine(i, i+N, 1, -1);
            AddLine(i+N, Sink, 1, 0);
        }
        for(int i=0; i<M; i++) {
            scanf("%d %d", &From, &To);
            AddLine(From+N, To, 1, 0);
        }
        printf("%d\n", -MCMF(Sour, Sink));
    }
}

 

위의 구상 아이디어를 풀이 코드로 구현하면 위와 같이 됩니다.

AddLine 함수를 구현해서 간선과 Capacity, Cost를 한 번에 추가해주는 방법이 아무래도 훨씬 편한 것 같습니다.