[C++ 백준 풀이] 15892번 : 사탕 줍는 로봇 / 17222번 : 위스키 거래 / 1258번 : 문제 할당

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 15892번 : '사탕 줍는 로봇', 17222번 : '위스키 거래', 1258번 : '문제 할당'의 풀이 코드와 해설을 다루고 있습니다.

 

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

 

 

15892번 : 사탕 줍는 로봇

15892번: 사탕 줍는 로봇

 

n개의 방과 m개의 복도에 대해, 특정 복도들에 특정 개수의 사탕을 배치하고 로봇들이 사탕을 주우면서 마지막 방으로 도착하게 할 때 로봇을 최대 몇 대 보낼 수 있는지 구하는 문제입니다.

전형적인 최대 유량 알고리즘 문제이므로, 정석 코드대로 풀이해주면 됩니다.

 

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

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 305
#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 Count = 0;
    while(true) {
        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(Next == Sink) break;
                }
            }
        }
        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;
        }
        Count += Amount;
    }
    return Count;
}

int main() {
    int N, M, A, B, Amount;
    scanf("%d %d", &N, &M);
    int SINK = N;
    for(int i=0; i<M; i++) {
        scanf("%d %d %d", &A, &B, &Amount);
        Line[A].push_back(B), Line[B].push_back(A);
        Capacity[A][B] += Amount;
        Capacity[B][A] += Amount;
    }
    printf("%d", MaxFlow(SOUR, SINK));
}

 

주의할 점은, Capacity 설정할 때 Capacity[A][B] = Capacity[B][A] = Amount로 설정하면 오답 처리를 받습니다.

그 이유는 같은 복도에 대해 입력이 추가로 더 주어질 수도 있기 때문입니다.

같은 알고리즘을 배워도 정석 코드대로 제대로 배워야 하는 이유입니다.

 

 

 

 

17222번 : 위스키 거래

 

문제가 길지만 요약하자면 정해진 규칙대로의 유통망 내에서 위스키를 최대로 보낼 수 있는 양을 구하는 문제입니다.

이런 조건이 많은 문제는 조건을 하나라도 놓치면 시간이 많이 날아가기 때문에 처음에 읽을 때 조건을 단 하나라도 놓치지 않도록 꼼꼼히 읽는 것이 중요한 것 같습니다.

제가 놓쳤던 포인트는 명진이의 친구들은 명진이의 친구들에게도 위스키를 보낼 수 있다는 것이었습니다.

 

 

 

그래프의 구성을 모식도로 나타내면 위와 같습니다.

위의 그래프를 그대로 구현만 해서 Max Flow 알고리즘을 돌려주기만 하면 됩니다.

 

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

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

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

long long MaxFlow(int Sour, int Sink) {
    long long Count = 0;
    while(true) {
        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(Next == Sink) break;
                }
            }
        }
        if(!Parent[Sink]) break;

        long long 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;
        }
        Count += Amount;
    }
    return Count;
}

int main() {
    int N, M, K, Node;
    scanf("%d %d", &N, &M);
    int Sour = N+M+1, Sink = N+M+2;
    vector<long long> CapacityN(N+1);
    for(int i=1; i<=N; i++) scanf("%lld", &CapacityN[i]);
    for(int i=N+1; i<=N+M; i++) {
        Line[Sour].push_back(i), Line[i].push_back(Sour);
        scanf("%lld", &Capacity[Sour][i]);
    }
    for(int i=1; i<=N; i++) {
        Line[i].push_back(Sink), Line[Sink].push_back(i);
        Capacity[i][Sink] = INF;
    }
    for(int i=N+1; i<=N+M; i++) {
        scanf("%d", &K);
        for(int j=0; j<K; j++) {
            scanf("%d", &Node);
            Line[i].push_back(Node), Line[Node].push_back(i);
            if(Node <= N) Capacity[i][Node] = CapacityN[Node];
            else Capacity[i][Node] = Capacity[Sour][Node];
        }
    }
    printf("%lld", MaxFlow(Sour, Sink));
}

 

 

 

 

1258번 : 문제 할당

 

N명의 학생들이 N개의 문제를 풀 때 각자 푸는 시간이 정해져있다고 했을 때, 각자 1문제씩 할당시켜서 푸는 시간의 합을 최소로 만들기 위해서 어떻게 배정해야 하고 그 때 풀이 시간의 총합을 구하는 문제입니다.

이 문제는 최대 유량과는 관계가 없어보이지만 노드 간의 연결만 잘 구성하면 최소 비용 최대 유량 알고리즘으로으로 풀이가 가능합니다.

 

 

 

Sour와 Sink 노드는 추가적으로 생성을 해주고, 왼쪽에 학생들의 번호에 대응되는 N개의 노드와 오른쪽에 문제들의 번호에 대응되는 N개의 노드를 생성하여 가운데를 T_ij로 연결해주면 됩니다.

비용 자체는 학생과 문제 사이에만 time으로써 연결되므로, 최소 비용 최대 유량 알고리즘으로 해결이 가능합니다.

 

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

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

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

int MCMF(int Sour, int Sink) {
    int CostSum = 0;
    while(true) {
        bool isInQueue[MAX] = {};
        int Parent[MAX] = {}, Dist[MAX];
        fill(Dist, Dist+MAX, INF);
        Dist[Sour] = 0;

        queue<int> Queue;
        Queue.push(Sour);
        isInQueue[Sour] = true;

        while(!Queue.empty()) {
            int Cur = Queue.front();
            Queue.pop();
            isInQueue[Cur] = false;
            for(int i=0; i<Line[Cur].size(); i++) {
                int Next = Line[Cur][i];
                if(Capacity[Cur][Next] - Flow[Cur][Next] > 0
                   && Dist[Cur] + SinDist[Cur][Next] < Dist[Next]) {
                    Dist[Next] = Dist[Cur] + SinDist[Cur][Next];
                    Parent[Next] = Cur;
                    if(!isInQueue[Next]) {
                        Queue.push(Next);
                        isInQueue[Next] = true;
                    }
                }
            }
        }
        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]) {
            CostSum += SinDist[Parent[i]][i];
            Flow[Parent[i]][i] += Amount;
            Flow[i][Parent[i]] -= Amount;
        }
    }
    return CostSum;
}

int main() {
    int N;
    scanf("%d", &N);
    int Sour = 2*N+1, Sink = 2*N+2;
    for(int i=1; i<=N; i++) {
        Line[Sour].push_back(i), Line[i].push_back(Sour);
        Capacity[Sour][i] = 1;
    }
    for(int i=N+1; i<=2*N; i++) {
        Line[i].push_back(Sink), Line[Sink].push_back(i);
        Capacity[i][Sink] = 1;
    }
    for(int i=1; i<=N; i++) {
        for(int j=N+1; j<=2*N; j++) {
            Line[i].push_back(j), Line[j].push_back(i);
            Capacity[i][j] = 1;
            scanf("%d", &SinDist[i][j]);
            SinDist[j][i] = -SinDist[i][j];
        }
    }
    printf("%d", MCMF(Sour, Sink));
}

 

 

 

풀이를 제출해보면 굉장히 여유있는 시간에 통과가 가능합니다.

문제 제한 시간이 5초나 되는데 12ms에 풀리는 것을 보면, 이 문제는 브루트포스 비슷하게 구현해도 풀릴 수도 있겠다 싶습니다.