[C++ 백준 풀이] 2367번 : 파티 (최대 유량 알고리즘)

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

 

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

 

[C++ 알고리즘] 최대 유량 알고리즘 (Network Flow, Ford-Fulkerson, Edmonds-Karp)

최대 유량 알고리즘에 대한 설명은 위의 링크에 정리되어 있으니 참고하시면 유용할 것입니다.

 

 

2367번 : 파티

2367번: 파티

 

다음과 같은 규칙에 따라 음식들을 가져온다고 할 때, 가져올 수 있는 음식의 최대 수를 구하는 문제입니다.

- 사람 당 가져올 수 있는 음식의 수는 K개입니다.

- 한 사람은 한 가지 종류의 음식은 최대 1개까지만 가져올 수 있습니다.

- 각 사람마다 요리할 수 있는 음식의 종류는 한정적이며, 이는 입력으로 주어집니다.

- 각 음식마다 합쳐서 가져올 수 있는 양 역시 한정적이며, 이는 입력으로 주어집니다.

 

 

이러한 유형의 문제는 최대 유량 알고리즘, 네트워크 플로우 알고리즘을 사용해 풀이할 수 있습니다.

이를 적절히 연결시켜 나타낸 것이 위의 그림이고, 노드 위치의 숫자는 노드의 번호를 말하며 왼쪽에 일렬로 나열된 노드들 사람, 오른쪽 그룹은 음식에 대응됩니다.

 

Sour 노드와 Sink 노드만 임의로 만들어주고, 모든 노드들을 정의하여 Sour 노드에서 나가 Sink 노드로 도달되도록 적절히 연결해준 뒤 최대 유량을 구하면 되므로, 문제 상황을 최대한 위와 같은 그래프에 끼워맞추도록 해봅니다.

그러면 3번 노드에서부터 2+N번 노드까지는 사람에 해당되는 노드, 3+N번 노드부터 2+N+D번 노드까지는 음식에 해당되는 노드라고 할 수 있습니다.

Sour에서 사람을 가리키는 간선은 사람 당 최대 가져갈 수 있는 음식 수를 대응시켜주면 되며, 사람에서 음식을 가리키는 간선은 각 사람이 할 수 있는 음식의 종류로 대응시켜 연결해주면 되고, 마지막으로 음식에서 Sink를 가리키는 간선은 각 음식별로 들고 갈 수 있는 음식 수의 최댓값을 대응시켜주면 됩니다.

 

 

 

부연 설명을 위해 예제 입력에 대한 답만 그려보자면, 위와 같이 나타낼 수 있습니다.

각 사람마다 가져올 수 있는 음식의 수는 최대 3이고 각 음식은 순서대로 2, 2, 2, 2, 3개만 가져갈 수 있으므로 그 안에서 최댓값을 찾으면 위의 빨간색으로 표시한 것과 같은 형태로 선택하여 9개의 음식을 가져갈 수 있게 됩니다.

그렇다면 이 노드와 간선들의 구성을 직접 코드로 구현해보도록 하겠습니다.

 

 

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

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

int MaxFlow(int Sour, int Sink) {
    int Sum = 0;
    while(1) {
        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(!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;
        }
        Sum += Amount;
    }
    return Sum;
}

int main() {
    int N, K, D, A, B, Value, F;
    scanf("%d %d %d", &N, &K, &D);
    for(int i=3; i<N+3; i++) {
        Line[SOUR].push_back(i), Line[i].push_back(SOUR);
        Capacity[SOUR][i] = K;
    }
    for(int i=N+3; i<N+D+3; i++) {
        Line[i].push_back(SINK), Line[SINK].push_back(i);
        scanf("%d", &Value);
        Capacity[i][SINK] = Value;
    }
    for(int i=3; i<N+3; i++) {
        scanf("%d", &F);
        for(int j=0; j<F; j++) {
            scanf("%d", &Value);
            Line[i].push_back(N+2+Value), Line[N+2+Value].push_back(i);
            Capacity[i][N+2+Value] = 1;
        }
    }
    printf("%d", MaxFlow(SOUR, SINK));
}

 

코드의 구현 자체는 사실 이전에 다루었던 최대 유량 알고리즘의 구현(이 포스트에서 맨 윗부분에 첨부된 링크의 포스트)과 거의 동일합니다.

main 함수에서는 주어진 입력을 이용해 노드들을 정의하고 이들 사이의 간선을 연결하며, Capacity를 제한시켜 주는 기능이 구현되어 있습니다.

MaxFlow 함수에서는 main 함수에서의 입력을 바탕으로 최대 유량 알고리즘을 적용시켜 Sour에서 Sink로 도달할 수 있는 최대 유량을 계산하여 반환해줍니다.

 

 

 

위의 코드대로 알고리즘을 작성하여 제출해보면 24ms의 시간을 소요하고 정답 처리를 받을 수 있습니다.