[C++ 백준 풀이] 5997번 : Who Brings the Cookies? / 2679번 : 맨체스터의 도로

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 5997번 : 'Who Brings the Cookies?', 2679번 : '맨체스터의 도로' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

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

 

 

5997번 : Who Brings the Cookies?

5997번: Who Brings the Cookies?

 

문제를 해석해보면, N마리의 소가 M개의 그룹에 속해있고, 각 그룹에 대해 어떤 소가 속해있는지를 입력받습니다.

그리고 각 그룹별로 한 마리의 소가 쿠키를 준비해오는데, 한 마리의 소는 소속되어 있는 그룹의 번호가 i인 그룹의 소속되어 있는 소의 수를 C_i라고 할 때, sum(1/Ci)를 올림한 값 이하로 쿠키를 준비해온다는 조건이 있습니다.

이 때 각 그룹에 대해 어떤 수가 쿠키를 준비해올지를 결정하는 문제입니다. (위의 조건만 만족하면 되기 때문에 답은 여러가지가 나올 수 있는데 이들 중 하나만 출력하면 됩니다.

 

 

 

최대 유량 알고리즘으로 해결할 수 있습니다.

다만 각 그룹별 소속되어 있는 소의 수를 구해 공식에 대입해야 하므로 그 과정이 귀찮습니다.

그룹별 소의 수만 구해준다면 Limit 배열에 각 소들이 최대로 가져올 수 있는 쿠키의 수를 구할 수 있고, 그것을 Sour와 소의 번호에 대응되는 노드 사이의 유량으로 설정해주면 됩니다.

그리고 소와 그룹 사이의 간선 연결은 소가 참석하는 그룹에만 연결을 수행해주고 그 용량은 모두 1로 설정해주면 됩니다.

넘버링은 위와 같이 진행 후 최대 유량을 구하여 그것이 M일 때 소와 그룹 간의 Flow를 찾아주면 됩니다.

만약 최대 유량이 M보다 작다면 조건을 만족시키는 해가 없는 것이므로 -1을 출력해주면 됩니다.

 

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

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

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];
        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, Cow, GroupSize[105] = {}, Limit[1005] = {};
    scanf("%d %d", &N, &M);
    int Sour = N+M+1, Sink = N+M+2;
    vector<int> GroupList[1005];
    for(int i=1; i<=M; i++) {
        scanf("%d", &GroupSize[i]);
        for(int j=0; j<GroupSize[i]; j++) {
            scanf("%d", &Cow);
            GroupList[Cow].push_back(i);
        }
    }
    for(int i=1; i<=N; i++) {
        double L = 0;
        for(int j=0; j<GroupList[i].size(); j++) L += 1.0/GroupSize[GroupList[i][j]];
        Limit[i] = (int)ceil(L);
    }
    for(int i=1; i<=N; i++) {
        Line[Sour].push_back(i), Line[i].push_back(Sour);
        Capacity[Sour][i] = Limit[i];
    }
    for(int i=1; i<=N; i++) {
        for(int j=0; j<GroupList[i].size(); j++) {
            int G = GroupList[i][j];
            Line[i].push_back(N+G), Line[N+G].push_back(i);
            Capacity[i][N+G] = 1;
        }
    }
    for(int i=N+1; i<=N+M; i++) {
        Line[i].push_back(Sink), Line[Sink].push_back(i);
        Capacity[i][Sink] = 1;
    }
    if(MaxFlow(Sour, Sink) == M) {
        for(int j=N+1; j<=N+M; j++)
            for(int i=1; i<=N; i++)
                if(Flow[i][j] == 1) printf("%d\n", i);
    }
    else printf("-1");
}

 

위의 설명을 풀이 코드로 작성한 것이 위의 코드입니다.

대부분 최대 유량 알고리즘을 그대로 사용한 것이며, 그나마 다른 부분 역시 배열 몇 개를 더 선언하여 소의 수를 카운트해주는 부분뿐이라 크게 어렵지 않습니다.

 

 

 

 

2679번 : 맨체스터의 도로

 

그래프가 주어지고 A에서 B로 가는 최대 유량과, 하나의 경로 중 최대 유량의 비를 구하는 문제입니다.

최대 유량은 기존에 다루었던 최대 유량 알고리즘의 최대 유량을 말하는 것이고, 하나의 경로 중 최대 유량의 경우에는 다른 방식으로 구해주어야 함을 예상할 수 있습니다.

 

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

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

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

int MaxFlow() {
    int FlowSum = 0;
    while(true) {
        int Prev[MAX];
        fill(&Prev[0], &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 MaxRoute[MAX];
int MaxAmount(int Curr) {
    int &Amount = MaxRoute[Curr];
    if(Amount != -1) return Amount;
    if(Curr == Sink) return Amount = INF;
    Amount = 0;
    for(int i=0; i<Line[Curr].size(); i++) {
        int Next = Line[Curr][i];
        Amount = max(Amount, min(MaxAmount(Next), Capacity[Curr][Next]));
    }
    return Amount;
}

int main() {
    int T, N, E, A, B, Amount;
    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);
        fill(&MaxRoute[0], &MaxRoute[MAX], -1);
        for(int i=0; i<MAX; i++) vector<int>().swap(Line[i]);
        scanf("%d %d %d %d", &N, &E, &Sour, &Sink);
        for(int i=0; i<E; i++) {
            scanf("%d %d %d", &A, &B, &Amount);
            Line[A].push_back(B), Line[B].push_back(A);
            Capacity[A][B] += Amount;
        }
        printf("%.3lf\n", (double)MaxFlow()/MaxAmount(Sour));
    }
}

 

테스트케이스가 존재하는 문제이므로 외곽에 반복문을 하나 구현해주며, 동시에 각 배열과 벡터를 fill 함수 등으로 초기화 해줍니다.

최대 유량은 MaxFlow 함수로 구현이 되어있고, 문제가 되는 부분은 MaxAmount 함수입니다.

DFS를 이용하여 모든 루트를 탐색하되 각 경로의 간선 중에서는 최소를 기록하고, 모든 경로의 Amount 중에서는 최대를 기록하여 (경로의 최솟값의 최댓값) 최대 유량을 가진 경로의 Amount를 반환해주면 됩니다.

 

 

 

제출해보면 위와 같이 짧은 시간 안에 모든 테스트케이스를 통과함을 확인할 수 있습니다.