[C++ 백준 풀이][Diamond V] 3692번 : 펭귄들의 행진 (최대 유량 알고리즘)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 3692번 : '펭귄들의 행진'의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Diamond V에 해당하며 문제를 풀이하기 위해 최대 유량 알고리즘(Network Flow)에 대한 이해가 필요합니다.

 

 

3692번 : 펭귄들의 행진

3692번: 펭귄들의 행진

 

문제가 길어서 작은 캡쳐본에 내용을 모두 담는 것이 불가능합니다. 이미지의 설명이 부족하면 링크를 통해 문제 전문을 읽어보시는 것이 낫습니다.

문제를 요약하면 펭귄들은 도약 거리 이하의 거리에 있는 얼음으로만 이동이 가능하고, 각 얼음마다 도약할 수 있는 횟수의 제한이 주어질 때, 주어진 얼음들 중 모든 펭귄이 하나로 모일 수 있는 얼음들의 목록을 출력하는 문제입니다.

 

 

 

아이디어를 모식도로 나타내면 위와 같이 나타낼 수 있습니다.

핵심은 Sour와 Sink를 어떤 노드와 언제 연결할지를 선택하는 것입니다.

펭귄의 이동을 흐르는 유량으로 생각해봅시다.

먼저 Sour 노드에서의 연결은, 펭귄이 있는 얼음만을 시작점으로 잡아주는 과정을 통해 연결할 수 있습니다.

이 문제를 해결하기 위해서는 어쩔 수 없이 모든 얼음에 대해 각각 이 얼음으로 모든 펭귄이 모일 수 있는지 따로 계산을 해보아야 합니다.

즉 Sink 노드로의 연결은, for문을 돌리면서 하나씩 연결했다가 끊어주는 과정을 통해 이 노드에 모든 펭귄들이 모일 수 있는지를 각각 확인할 수 있습니다.

 

나머지 아이디어는 노드의 분할을 통해 노드 방문 횟수가 정해져 있는 경우 유량 문제로 해결할 수 있게 되는 아이디어인데 이것은 이미 이전에 다룬 적이 있습니다. (아래 링크의 '도시 왕복하기 2' 문제에 해당합니다.)

각각의 얼음에 대해 in, out 얼음을 따로 구성해야 하므로 번호를 헷갈리지 않고 정확히 매기도록 해야합니다.

저의 경우에는 x번 얼음의 out 노드는 x+N번으로 구성하였습니다.

 

[C++ 백준 풀이] 10976번 : 피난 / 17412번 : 도시 왕복하기 1 / 2316번 : 도시 왕복하기 2

 

이제 위의 모식도를 코드로 직접 구현해봅시다.

 

 

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

int Sour, Sink, Penguin;
int Capacity[MAX][MAX], Flow[MAX][MAX];
vector<int> Line[MAX];

int MaxFlow() {
    int FlowSum = 0;
    while(true) {
        int Prev[MAX];
        fill(Prev, Prev+MAX, -1);
        queue<int> Queue;
        Queue.push(Sour);
        while(!Queue.empty()) {
            int Curr = Queue.front();
            Queue.pop();
            for(int i=0; i<Line[Curr].size(); i++) {
                int Next = Line[Curr][i];
                if(Capacity[Curr][Next] - Flow[Curr][Next] > 0 && Prev[Next] == -1) {
                    Queue.push(Next);
                    Prev[Next] = Curr;
                }
            }
        }
        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]) {
            Flow[Prev[i]][i] += Amount;
            Flow[i][Prev[i]] -= Amount;
        }
        FlowSum += Amount;
    }
    return FlowSum;
}

int main() {
    int T, N, Check;
    double D;
    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);
        for(int i=0; i<MAX; i++) vector<int>().swap(Line[i]);
        scanf("%d %lf", &N, &D);
        Sour = 2*N, Sink = 2*N+1, Penguin = 0, Check = 0;
        int x[MAX], y[MAX], n, m;
        for(int i=0; i<N; i++) {
            scanf("%d %d %d %d", &x[i], &y[i], &n, &m);
            for(int j=0; j<i; j++) {
                if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) <= D*D) {
                    Line[i].push_back(j+N), Line[j+N].push_back(i);
                    Line[j].push_back(i+N), Line[i+N].push_back(j);
                    Capacity[i+N][j] = Capacity[j+N][i] = INF;
                }
            }
            if(n > 0) {
                Line[Sour].push_back(i), Line[i].push_back(Sour);
                Capacity[Sour][i] = n;
                Penguin += n;
            }
            Line[i].push_back(i+N), Line[i+N].push_back(i);
            Capacity[i][i+N] = m;
        }

        for(int i=0; i<N; i++) {
            fill(&Flow[0][0], &Flow[MAX-1][MAX], 0);
            Line[i].push_back(Sink), Line[Sink].push_back(i);
            Capacity[i][Sink] = INF;
            if(MaxFlow() == Penguin) {
                printf("%d ", i);
                Check = 1;
            }
            Line[i].pop_back(), Line[Sink].pop_back();
            Capacity[i][Sink] = 0;
        }
        if(!Check) printf("-1");
        printf("\n");
    }
}

 

풀이 코드는 위와 같고, 테스트케이스의 수만큼 코드가 반복되어야 하므로 Capacity나 Flow, Line과 같은 배열이나 벡터를 초기화해주어야 합니다.

좌표를 입력받아 거리 조건이 맞는 경우 노드 사이에 연결을 수행해주면 되고 그 뒤로는 좌표가 다시는 필요 없습니다.

i=0~N-1의 모든 얼음에 대해 MaxFlow 함수를 따로 돌려주면서 펭귄을 최대한 이동시켰을 때 총 펭귄의 수만큼 모였는지 유량을 통해 확인해줍니다.

모두 모인 경우는 그 얼음의 번호를 출력해주면 되고, 단 하나의 얼음에도 전부 모일 수가 없는 경우 문제 조건대로 -1을 출력해주면 됩니다.

 

어쨌든 핵심 아이디어는 최대 유량 알고리즘이기에 나머지 아이디어들은 크게 설명하지 않아도 최대 유량 알고리즘을 알고 있다면 어렵지 않습니다.

 

 

 

채점 결과는 위와 같으며 소요 시간을 보았을 때 별로 효율적인 코드는 아닌 것 같습니다.

(그래도 제가 배운 최대 유량 알고리즘으로는 이 정도가 최선이라고 생각합니다.)