[백준/BOJ C++] 1658번 : 돼지 잡기 (최대 유량, Network Flow)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 1658번 : '돼지 잡기' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

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

 

 

1658번 : 돼지 잡기

 

손님 N명이 순서대로 도착해서 각각이 가지고 있는 특정 번호들의 열쇠로 우리를 열고 돼지를 원하는 마릿수 이하로 가져간 뒤, 최근에 열린 우리 사이의 돼지들을 적절히 이동시킬 수 있다고 할 때 모든 사람들의 최대로 가져갈 수 있는 돼지의 합을 구하는 문제입니다.

 

 

 

이 문제의 핵심은 A, B번 사람이 같은 우리의 키를 가지고 있는 경우 B가 돼지를 더 많이 살 수 있도록 하기 위해 A가 덜 사는 과정을, B에서 A로 유량을 보내는 것으로 바꿔서 생각하는 것입니다.

최대 유량으로 문제를 해결하기 위해 문제 조건에 맞게 생각을 바꿔주는 것이 핵심입니다.

나머지는 일반적인 최대 유량 문제와 같이 적절히 사람과 돼지 우리 간의 노드를 연결하는 간선들을 구현하여 최대 유량 알고리즘만 사용해주면 됩니다.

 

 

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

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

void AddLine(int From, int To, int Amount) {
    Line[From].push_back(To), Line[To].push_back(From);
    Capacity[From][To] = Amount;
}

int MaxFlow(int Sour, int Sink) {
    int FlowSum = 0;
    while(true) {
        int Parent[MAX];
        fill(Parent, Parent+MAX, -1);
        queue<int> Queue;
        Queue.push(Sour);
        Parent[Sour] = Sour;
        while(!Queue.empty()) {
            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] == -1) {
                    Queue.push(Next);
                    Parent[Next] = Cur;
                }
            }
        }
        if(Parent[Sink] == -1) 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, M, K, A, B, Amount, KeyNum;
    scanf("%d %d", &M, &N);
    int Sour = N+M+1, Sink = N+M+2;
    for(int i=N+1; i<=N+M; i++) {
        scanf("%d", &Amount);
        AddLine(i, Sink, Amount);
    }
    vector<int> KeyList[MAX];
    for(int i=1; i<=N; i++) {
        scanf("%d", &K);
        for(int j=0; j<K; j++) {
            scanf("%d", &KeyNum);
            AddLine(i, N+KeyNum, INF);
            KeyList[KeyNum].push_back(i);
        }
        scanf("%d", &Amount);
        AddLine(Sour, i, Amount);
    }
    for(int i=1; i<=M; i++) {
        if(!KeyList[i].size()) continue;
        for(int j=0; j<KeyList[i].size()-1; j++) {
            int Curr = KeyList[i][j];
            for(int k=j+1; k<KeyList[i].size(); k++) {
                int Next = KeyList[i][k];
                AddLine(Next, Curr, INF);
            }
        }
    }
    printf("%d", MaxFlow(Sour, Sink));
}

 

나머지 코드는 일반적이지만, 이 문제에서는 각 돼지 우리 키를 가지는 사람들의 번호를 뽑는 과정이 추가됩니다.

따라서 vector를 하나 생성하여 특정 번호의 키를 가지고 있는 사람들의 번호를 push_back 해주고, 같은 우리 키를 가진 사람 순서쌍을 뽑아 뒷 번호 사람으로부터 앞 번호 사람에 flow를 보내주도록 구현해줍니다.