[C++ 백준 풀이] 1585번 : 경찰 / 2365번 : 숫자판 만들기 (MCMF + 최대 유량 알고리즘)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 1585번 : '경찰', 2365번 : '숫자판 만들기'의 풀이 코드와 해설을 다루고 있습니다.

 

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

 

 

1585번 : 경찰

1585번: 경찰

 

기존 최소 비용 최대 유량 문제들에 비해 고려해야할 요소들이 많아서 상당히 귀찮았던 문제입니다.

차가 들어가는 시간들과 나오는 시간들을 적절히 조합하여, 과속인 경우 제한 시간과의 차이의 제곱을 벌금으로 징수할 수 있으며 이 때 가능한 벌금의 최솟값과 최댓값을 구하는 문제입니다.

 

 

 

문제를 MCMF 알고리즘에 맞춰 풀이하도록 그래프를 구성하기 위해, 위와 같이 아이디어를 구상하였습니다.

왼쪽 노드에는 들어가는 시간들을, 오른쪽 노드에는 나오는 시간들에 대응되도록 노드를 잡고 이들 중 Out - In > 0인 노드들만 간선으로 연결하여 그 경로들을 모두 찾는 것입니다.

이 때 간선의 비용은 min((T-(out-in))^2, F)로 하여 F보다 작은 경우는 주어진 벌금대로 징수하고 F보다 큰 경우에는 F의 벌금을 부과하도록 하였습니다.

 

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

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

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

int MCMF(int Sour, int Sink) {
    int Count = 0, CostSum = 0;
    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] + SinDist[Cur][Next] < Dist[Next]) {
                    Dist[Next] = Dist[Cur] + SinDist[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*SinDist[Parent[i]][i];
            Flow[Parent[i]][i] += Amount;
            Flow[i][Parent[i]] -= Amount;
        }
        Count++;
    }
    if(Count < N) return -1;
    else return CostSum;
}

int main() {
    int T, F;
    scanf("%d", &N);
    int Sour = 2*N+1, Sink = 2*N+2;
    for(int i=1; i<=N; i++) {
        Line[Sour].push_back(i), Line[i].push_back(Sour);
        Capacity[Sour][i] = 1;
    }
    for(int i=N+1; i<=2*N; i++) {
        Line[i].push_back(Sink), Line[Sink].push_back(i);
        Capacity[i][Sink] = 1;
    }
    vector<int> In(N+1), Out(2*N+1);
    for(int i=1; i<=N; i++) scanf("%d", &In[i]);
    for(int i=N+1; i<=2*N; i++) scanf("%d", &Out[i]);
    scanf("%d %d", &T, &F);
    for(int i=1; i<=N; i++) {
        for(int j=N+1; j<=2*N; j++) {
            if(Out[j] > In[i]) {
                Line[i].push_back(j), Line[j].push_back(i);
                Capacity[i][j] = 1;
            }
            if(Out[j]-In[i] < T) {
                SinDist[i][j] = min((T-(Out[j]-In[i]))*(T-(Out[j]-In[i])), F);
                SinDist[j][i] = -SinDist[i][j];
            }
        }
    }
    int Ans = MCMF(Sour, Sink);
    printf("%d ", Ans);
    if(Ans < 0) return 0;

    fill(&Flow[0][0], &Flow[MAX-1][MAX], 0);
    for(int i=1; i<=N; i++)
        for(int j=N+1; j<=2*N; j++) {
            SinDist[i][j] = -SinDist[i][j];
            SinDist[j][i] = -SinDist[j][i];
        }
    printf("%d", -MCMF(Sour, Sink));
}

 

일반적으로 최소 비용 최대 유량 알고리즘은 최소 비용을 구하기 때문에, 최대 비용을 구하기 위해서는 Flow 값을 초기화해주고 모든 dist 값을 음수로 바꾸어 다시 계산한 뒤, 나온 최소 비용 값에 다시 음수를 붙여 구하는 방식으로 해결하였습니다.

이러한 아이디어는 이전에 풀이했던 '열혈강호' 문제에서도 등장했던 아이디어입니다.

 

 

 

 

2365번 : 숫자판 만들기

2365번: 숫자판 만들기

 

위의 그림과 같이 각 행의 합과 각 열의 합이 주어졌을 때 숫자판을 구성할 수 있는 숫자들 중 최댓값이 가장 작은 조합의 최댓값과 그 때의 숫자판의 배열을 구하는 문제입니다.

이 문제 역시 간단하게만 생각하면 최대 유량 알고리즘으로 해결할만한 아이디어가 쉽게는 보이지 않습니다.

다만 최대 유량 알고리즘으로 해결할 수 있다는 정보가 주어지면 그에 적절한 조건들을 그래프로 끼워맞춰서 풀이하는 것은 아래와 같이 해볼 수 있습니다.

 

 

 

이 문제의 풀이에 아이디어에 대한 모식도는 위와 같습니다.

노드들의 Numbering 과정은 일반적인 최대 유량 알고리즘의 방식과 같습니다.

다만 각 Row의 합을 왼쪽 노드들로, 각 Col의 합을 오른쪽 노드들로 분리한 뒤 Sour에서 왼쪽 노드들로의 Capacity는 Row Sum, 오른쪽 노드들에서 Sink로의 Capacity는 Col Sum으로 설정해줌으로써 문제를 해결하기 위한 그래프를 설계할 수 있습니다.

Row가 Col 사이의 모든 노드들을 연결한 뒤 적절한 Max 값을 설정하여 그 때의 최대 유량이 Row Sum들의 합(= Col Sum들의 합)과 같다면 해당 Max 값을 최댓값으로 갖는 숫자판의 조합이 존재하는 것입니다.

 

따라서 이 Max 값을 입력 범위인 1과 10000 사이에서 적절히 이분탐색으로 세팅해보면서 최소의 Max가 무엇인지 찾으면 제한 시간 안에 문제를 해결할 수 있습니다.

 

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

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

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

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;
    scanf("%d", &N);
    int Sour = 2*N+1, Sink = 2*N+2;
    for(int i=1; i<=N; i++) {
        Line[Sour].push_back(i), Line[i].push_back(Sour);
        scanf("%d", &Capacity[Sour][i]);
        Sum += Capacity[Sour][i];
    }
    for(int i=N+1; i<=2*N; i++) {
        Line[i].push_back(Sink), Line[Sink].push_back(i);
        scanf("%d", &Capacity[i][Sink]);
    }
    for(int i=1; i<=N; i++)
        for(int j=N+1; j<=2*N; j++)
            Line[i].push_back(j), Line[j].push_back(i);
    int Left = 0, Right = 10000, Mid, Ans;
    while(Left <= Right) {
        Mid = (Left + Right)/2;
        for(int i=1; i<=N; i++)
            for(int j=N+1; j<=2*N; j++) Capacity[i][j] = Mid;
        fill(&Flow[0][0], &Flow[MAX-1][MAX], 0);
        if(MaxFlow(Sour, Sink) == Sum) {
            Ans = Mid;
            Right = Mid-1;
        }
        else Left = Mid+1;
    }
    printf("%d\n", Ans);

    for(int i=1; i<=N; i++)
        for(int j=N+1; j<=2*N; j++) Capacity[i][j] = Ans;
    fill(&Flow[0][0], &Flow[MAX-1][MAX], 0);
    MaxFlow(Sour, Sink);
    for(int i=1; i<=N; i++) {
        for(int j=N+1; j<=2*N; j++) printf("%d ", Flow[i][j]);
        printf("\n");
    }
}

 

위 코드는 위의 아이디어 모식도에서 구상한 아이디어를 그대로 코드로 구현한 것입니다.

최대 유량 알고리즘을 이분탐색으로 여러 번 반복하는 것 외에는 달라지는 점이 없으므로, 코드를 따라가시면서 그대로 이해하시면 됩니다.

다만 MaxFlow를 매번 실행할 때마다 Flow 배열의 초기화가 필요하므로, fill을 활용하여 Flow 배열을 모두 0으로 초기화해주었습니다.

또한 마지막으로 시도하여 설정한 Max 값이 조건에 맞지 않는 경우도 존재하므로, Ans를 찾은 이후에는 Ans 값으로 MaxFlow 연산을 다시 수행해주도록 해야 합니다.