[백준/BOJ C++] 11410번 : 칙칙폭폭 (+ 백준 Solved.ac Platinum I 달성)

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

 

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

 

 

11410번 : 칙칙폭폭

11410번: 칙칙폭폭

 

기차가 1번 도시에서부터 운행을 시작하여 N번 도시까지 번호순대로 순차적으로 운행한다고 하고, 각 승객이 탈 위치와 내릴 위치, 그리고 그 비용이 주어졌을 때 최대 승객 용량이 P인 기차로 얻을 수 있는 수익의 최댓값을 구하는 문제입니다.

 

 

 

이 문제에서 가장 문제가 되는 핵심 포인트는 i에서 j로 간선을 연결하더라도 중간에 최대 기차 승객 수인 P를 넘어버리면 어떻게 하냐는 것입니다.

그러나 이것은 생각보다 간단하게 해결이 되는데, 그저 Sour 노드와 1번 도시에 대응되는 간선, 그리고 N번 도시에 대응되는 간선과 Sink 노드 사이 간선의 Capacity를 P로 설정해주면 해결이 됩니다.

이렇게 설정해주면 한 도시에서 P명보다 많은 사람이 기차에 탈 수가 없게 되고, 동시에 기차에 P명보다 많은 사람이 기차에 타는 순간이 결과로 얻어질 수 없습니다. (기차에서 내리기만 하는 사람은 없기 때문)

 

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 55
#define INF 100000000000
using namespace std;

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 Capacity, int Cost) {
    Edge* E = new Edge(To, Capacity, 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 Sour, int Sink) {
    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() {
    int N, P, Capacity[MAX][MAX], SinCost[MAX][MAX];
    scanf("%d %d", &N, &P);
    int Sour = N+1, Sink = N+2;
    AddLine(Sour, 1, P, 0);
    AddLine(N, Sink, P, 0);
    for(int i=1; i<N; i++) AddLine(i, i+1, INF, 0);
    for(int i=1; i<N; i++)
        for(int j=1; i+j<=N; j++) scanf("%d", &Capacity[i][i+j]);
    for(int i=1; i<N; i++)
        for(int j=1; i+j<=N; j++) {
            scanf("%d", &SinCost[i][i+j]);
            AddLine(i, i+j, Capacity[i][i+j], -SinCost[i][i+j]);
        }
    printf("%d", -MCMF(Sour, Sink));
}

 

풀이 코드는 위와 같고, 그래프를 그대로 연결만 해주면 됩니다.

이 문제에서는 비용의 최댓값을 구해야 하므로, 비용을 대입해주는 과정에서 마이너스 부호를 한 번, 그리고 결과 값을 출력하는 부분에서 마이너스 부호를 한 번 붙여줌으로써 MCMF 알고리즘으로 최댓값을 구할 수 있습니다.

 

 

 

위는 채점 결과이고, N이 50 이하로 아주 작기 때문에 채점 시간은 0에 수렴합니다.

 

 

 

---

Platinum I 승급

 

 

백준 Solved.ac 티어가 Platinum I로 승급되었으며, 레이팅 기준으로 랭킹이 670위가 되었습니다.

단기적인 목표는 Diamond 티어였기 때문에, 당분간 쉬다가 Diamond 티어까지 다시 문제들을 풀이해보겠습니다.