[C++ 백준 풀이] 11377번 : 열혈강호 3, 11378번 : 열혈강호 4 (최대 유량 알고리즘)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 11377번 : '열혈강호 3', 11378번 : '열혈강호 4' 문제의 풀이 코드와 해설에 대해 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum III에 해당하며, 문제를 풀이하기 위해 최대 유량 알고리즘에 대한 이해가 필요합니다. (다만 일반적인 풀이는 이분 매칭 알고리즘의 응용임을 참고해야 함)

 

 

11377번 : 열혈강호 3

11377번: 열혈강호 3

 

N명의 직원이 각각 할 수 있는 일의 후보가 주어지고, 이 중에서 K명만이 일을 최대 2개, 나머지 직원은 1개의 일만 할 수 있을 때, M개의 일 중에서 최대 몇 개의 일을 할 수 있는지 출력하는 문제입니다.

N명 중에서 어떤 사람이 어떤 일을 해야할지 배정을 하기 위해 모든 경우의 수를 고려한다면 그 경우의 수가 엄청나게 많아지기 때문에, 효율적인 알고리즘을 응용하여 풀이해야 하는 문제입니다.

일반적인 풀이 방법은 이분 매칭을 사용하여 풀이하는 것이지만, 여기서는 최대 유량 알고리즘을 사용하여 풀이하는 방법을 설명하도록 하겠습니다.

 

 

 

최대한 많은 수의 일을 수행할 수 있는 방법을 찾기 위해 최대 유량 알고리즘을 사용하기 위해서는, 노드들을 적절히 선언하여 최대 유량 알고리즘이 사용되도록 그래프의 연결 관계를 만들어주면 됩니다.

따라서 일의 수를 유량으로 생각하고, Sour, Node K, Sink의 3개의 임의의 노드를 선언하여 Sour에서 Sink까지 최대한 많은 유량을 보내기 위한 방법을 찾으면 됩니다.

여기서 Node K를 선언해 준 이유는 직원 중 K명이 2개의 일을 할 수 있기 때문에, 이 K개의 추가로 가능한 일의 할당량을 분배하기 위함입니다.

이것은 Sour에서 Node K에 K의 유량을 보내고, Node K에서 Capacity가 1인 N개의 단방향 그래프를 연결지음으로써 구현이 가능합니다.

그렇다면 이제 위의 그래프를 실제로 구현하고, 그 그래프에 최대 유량 알고리즘만 사용해주면 됩니다.

 

 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 2005
#define INF 1000000000
#define SOUR 1
#define SINK 2
#define NODE_K 3
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, M, K, W, WNum;
    scanf("%d %d %d", &N, &M, &K);
    Line[SOUR].push_back(NODE_K), Line[NODE_K].push_back(SOUR);
    Capacity[SOUR][NODE_K] = K;
    for(int i=4; i<N+4; i++) {
        Line[SOUR].push_back(i), Line[i].push_back(SOUR);
        Line[NODE_K].push_back(i), Line[i].push_back(NODE_K);
        Capacity[SOUR][i] = Capacity[NODE_K][i] = 1;
        scanf("%d", &W);
        for(int j=0; j<W; j++) {
            scanf("%d", &WNum);
            Line[i].push_back(N+3+WNum), Line[N+3+WNum].push_back(i);
            Capacity[i][N+3+WNum] = 1;
        }
    }
    for(int i=N+4; i<N+M+4; i++) {
        Line[SINK].push_back(i), Line[i].push_back(SINK);
        Capacity[i][SINK] = 1;
    }
    printf("%d", MaxFlow(SOUR, SINK));
}

 

위의 아이디어를 코드로 구현한 것은 위와 같습니다.

코드에서 MaxFlow 알고리즘 자체는 기존의 최대 유량 알고리즘 구현과 똑같기 때문에, MAX 변수 설정이나 그래프 연결 부분만 유의하여 구현해주면 됩니다.

저의 경우에는 Sour를 1, node K를 2, Sink를 3번 노드로 설정하였고 직원의 노드를 그 뒤에, 일의 노드를 그 뒤에 순서대로 번호를 부여하였습니다.

Line의 경우에는 단순한 그래프 연결이므로 양방향으로 연결해주고, Capacity의 경우에는 한쪽으로만 계산을 해야하므로 단방향으로 연결해주어야 합니다.

 

 

 

제출해보면 시간이 꽤 오래 걸림을 확인할 수 있습니다.

오래 걸린다고 표현한 이유는 이분 매칭이라는 다른 풀이가 존재하기 때문입니다.

당분간은 최대 유량 알고리즘에 대해 다루겠지만, 시간이 난다면 이분 매칭을 이용하여 풀이하는 방법도 정리해보도록 하겠습니다.

 

 

11378번 : 열혈강호 4

11378번: 열혈강호 4

 

입출력은 이전 문제와 같으므로 문제 부분만 가지고 왔습니다.

벌점 K점을 매겨서 추가된 벌점만큼의 일을 더 할 수 있다고 할 때, 최대 일의 양을 구하는 문제입니다.

만약 이전 문제를 이분 매칭으로 풀었다면 풀이 자체를 다시 구성해야 했겠지만, 여기서는 최대 유량 알고리즘으로 풀었기 때문에 아주 손쉽게 풀이할 수 있습니다.

 

잘 생각해보면, K라는 벌점은 위 문제에서의 node K에서 직원들에게 가는 유량에 해당하므로, 이 부분의 유량 제한이 사라졌으므로 Capacity만 1에서 K로 바꿔주면 끝납니다.

(Capacity[SOUR][i] = 1, Capacity[NODE_K][i] = 1;을 Capacity[SOUR][i] = 1, Capacity[NODE_K][i] = K; 으로 바꾸라는 뜻)

 

 

 

제출해보면 손쉽게 정답 처리를 받을 수 있습니다.