[백준/BOJ C++] 6241번 : Dining (Diamond V, 최대 유량 알고리즘)

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

 

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

 

 

6241번 : Dining

6241번: Dining

 

N마리의 소가 선호하는 Food들과 Drink들의 번호들이 입력으로 주어지고, 각 번호의 Food나 Drink는 한 소에게만 배정이 가능하다고 할 때, 최대 몇 마리의 소에게 원하는 번호의 음식과 음료의 배정이 가능한지를 구하는 문제입니다.

 

 

 

문제 분류 자체가 최대 유량으로 되어있어서 최대 유량으로 끼워맞추려고 생각해보면 됩니다.

핵심은 Food와 Drink를 모두 배정해야하기 때문에, Food에 대한 노드들과 Drink에 대한 노드들을 어떻게 Cow들에 대응되는 노드들에 연결시킬지를 고민해보는 것입니다.

생각해보면 위의 모식도와 같이 Cow에 대응되는 노드를 Food 노드들과 Drink 노드들 사이에 위치시켜주면 양쪽 모두에 연결이 가능합니다.

 

그리고 하나의 소에 대해서는 하나의 Food만 배정이 가능하므로 Cow 노드는 한 번씩만 방문되어야 합니다.

따라서 Cow 노드에 대해서 정점 분할을 수행해주어야 합니다.

그러면 최대 100인 노드 그룹의 수가 총 4개이므로, Sour와 Sink를 401, 402번으로 잡아주고 이 때 MAX는 402가 됩니다.

 

 

#include <bits/stdc++.h>
#define MAX 405
#define INF 1e9
using namespace std;

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

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

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);

        while(!Queue.empty() && Parent[Sink] == -1) {
            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 && Parent[Next] == -1) {
                    Queue.push(Next);
                    Parent[Next] = Curr;
                }
            }
        }
        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() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int N, F, D, Sour = 401, Sink = 402;
    cin >> N >> F >> D;

    for(int i=1; i<=F; i++) AddEdge(Sour, i);
    for(int i=1; i<=D; i++) AddEdge(300+i, Sink);
    for(int i=1; i<=N; i++) AddEdge(100+i, 200+i);

    for(int i=1; i<=N; i++) {
        int F_i, D_i, Node;
        cin >> F_i >> D_i;
        for(int j=0; j<F_i; j++) {
            cin >> Node;
            AddEdge(Node, 100+i);
        }
        for(int j=0; j<D_i; j++) {
            cin >> Node;
            AddEdge(200+i, 300+Node);
        }
    }

    cout << MaxFlow(Sour, Sink);
}

 

풀이 코드 자체는 위에 첨부한 모식도 그대로 그래프를 연결해주고, 네트워크 플로우 알고리즘을 수행해주기만 하면 되기 때문에 이론 자체는 어렵지 않습니다.

 

 

 

제출해보면 입력 범위가 작으므로 0ms의 채점 시간으로 정답 처리를 받는 것이 가능합니다.