[백준/BOJ C++] 18134번 : 치삼이의 대모험 / 17798번 : Estate Agent (최소 비용 최대 유량)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 18134번 : '치삼이의 대모험', 17798번 : 'Estate Agent' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

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

 

 

18134번 : 치삼이의 대모험

18134번: 치삼이의 대모험

 

문제를 요약하면, 노드와 노드 사이에 비용이 존재하고, 한 노드와 간선은 한 번씩만 지날 수 있을 때, 출발 노드와 도착 노드가 주어지면 최소 비용으로 왕복할 수 있는 경로의 비용을 구하는 문제입니다.

 

 

 

이 문제의 경우에는 모든 노드와 모든 간선을 한 번씩만 방문할 수 있으므로 모든 노드를 정점 분할 해주면 됩니다.

또한 출발 노드와 도착 노드가 임의로 주어지므로 그래프를 모두 구성한 뒤 마지막에 연결을 수행해주면 됩니다.

그리고 왕복 경로는 편도 경로를 두 개 구하는 것과 동일하므로, Sour에서 Sink로 경로가 겹치지 않도록 2회 이동하는 최소 비용을 구해주면 됩니다.

 

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

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

int N, M, L, U, V, Sour, Sink;
int Capacity[MAX][MAX] = {}, Flow[MAX][MAX] = {}, SinCost[MAX][MAX] = {};
vector<int> Line[MAX];

int in(int i) { return 2*i-1; }
int out(int i) { return 2*i; }

int MCMF() {
    int CostSum = 0;
    for(int i=0; i<2; i++) {
        int Parent[MAX]; fill(Parent, Parent+MAX, -1);
        int Cost[MAX]; fill(Cost, Cost+MAX, INF); Cost[Sour] = 0;
        queue<int> Queue; Queue.push(Sour);
        bool isInQueue[MAX] = {}; 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];
                    Parent[Next] = Curr;
                    if(!isInQueue[Next]) {
                        Queue.push(Next);
                        isInQueue[Next] = true;
                    }
                }
            }
        }
        if(Parent[Sink] == -1) { printf("-1"); exit(0); }

        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*SinCost[Parent[i]][i];
            Flow[Parent[i]][i] += Amount;
            Flow[i][Parent[i]] -= Amount;
        }
    }
    return CostSum;
}

int main() {
    scanf("%d %d", &N, &M);
    for(int i=0; i<M; i++) {
        scanf("%d %d %d", &L, &U, &V);
        Line[out(U)].push_back(in(V)), Line[in(V)].push_back(out(U));
        Line[out(V)].push_back(in(U)), Line[in(U)].push_back(out(V));
        Capacity[out(U)][in(V)] = Capacity[out(V)][in(U)] = 1;
        SinCost[out(U)][in(V)] = SinCost[out(V)][in(U)] = L;
        SinCost[in(U)][out(V)] = SinCost[in(V)][out(U)] = -L;
    }
    for(int i=1; i<=N; i++) {
        Line[in(i)].push_back(out(i)), Line[out(i)].push_back(in(i));
        Capacity[in(i)][out(i)] = 1;
    }
    scanf("%d %d", &Sour, &Sink);
    Sour = Sour*2, Sink = Sink*2-1;
    printf("%d", MCMF());
}

 

구현 자체는 일반적인 MCMF의 구현과 같으며, 단지 while문에서 2개의 경로만 탐색하는 식으로 바꿔주면 됩니다.

주의할 점은 경로가 존재하지 않는 경우도 테스트케이스에 주어지기 때문에, 이 경우는 -1을 출력하고 프로그램을 즉시 종료해주면 됩니다.

 

 

 

 

17798번 : Estate Agent

17798번: Estate Agent

 

N 가구의 가족들이 부동산 거래를 한다고 할 때 이들의 최대 거래 비용의 5%를 구하는 문제입니다.

문제에는 나와있지 않지만 상식적으로 접근하여, 가족 간에는 순환이 일어나듯 서로가 서로의 집을 옮길 수 있는 경우에만 거래 가능한 조건에 해당이 됩니다.

예를 들어 예제를 참고하여 예제 출력을 보면, 더 많은 중계비가 발생할 수 있음에도 4 1 6의 거래는 모든 가족이 한 가족 당 하나의 집으로 옮길 수 없게 되므로 발생하지 않습니다.

 

 

 

이 문제의 핵심 아이디어는 가족과 집에 대한 노드를 양 묶음으로 구현하고, 거래가 발생하지 않은 집은 그대로 0의 cost로 같은 가족에게 넘기는 것입니다.

그래야만 거래가 발생하지 않은 가족들까지 수를 합하여 유량을 확인할 수 있습니다.

최대 유량은 모든 가구의 거래가 발생하지 않은 경우인 N이므로, 최소 비용 최대 유량은 모든 가구가 집을 배정받으면서 최대한의 거래비를 계산할 수 있게 됩니다.

 

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

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

int N, M, L, U, V, Sour, Sink;

struct Edge {
    int Next, Capacity, Cost, Flow;
    Edge* Rev;
    Edge(int Next_, int Capacity_, int Cost_) : Next(Next_), Capacity(Capacity_), Cost(Cost_), Flow(0) {}
    int Remain() { return Capacity - Flow; }
    void AddFlow(int Amount) {
        Flow += Amount;
        Rev->Flow -= Amount;
    }
};
vector<Edge*> Line[MAX];

void AddLine(int From, int To, int Cost) {
    Edge* E = new Edge(To, 1, Cost);
    Edge* RevE = new Edge(From, 0, -Cost);
    E->Rev = RevE, RevE->Rev = E;
    Line[From].push_back(E), Line[To].push_back(RevE);
}

int MCMF() {
    int CostSum = 0;
    while(true) {
        Edge* Path[MAX];
        int Prev[MAX]; fill(Prev, Prev+MAX, -1);
        int Cost[MAX]; fill(Cost, Cost+MAX, INF); Cost[Sour] = 0;
        queue<int> Queue; Queue.push(Sour);
        bool inQueue[MAX] = {}; inQueue[Sour] = true;

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

        int Amount = INF;
        for(int i=Sink; i!=Sour; i=Prev[i])
            Amount = min(Amount, Path[i]->Remain());
        for(int i=Sink; i!=Sour; i=Prev[i]) {
            CostSum += Amount*Path[i]->Cost;
            Path[i]->AddFlow(Amount);
        }
    }
    return CostSum;
}

int main() {
    scanf("%d %d", &N, &M);
    Sour = N*2+1, Sink = N*2+2;
    for(int i=1; i<=N; i++) {
        AddLine(Sour, i, 0);
        AddLine(i, N+i, 0);
        AddLine(N+i, Sink, 0);
    }
    for(int i=0; i<M; i++) {
        scanf("%d %d %d", &U, &V, &L);
        AddLine(U, N+V, -L);
    }
    printf("%.7lf", -(double)MCMF()/20);
}

 

코드 자체는 역시 일반적인 MCMF 알고리즘과 동일하며, 단지 위의 모식도에서 나타낸대로 그래프를 연결 및 구현한 것이 전부입니다.

문제의 정답률을 보면 알겠지만 예외 처리나 다른 조치를 취하지 않아도 될 정도로 문제가 간단합니다.