[C/C++] 백준 #2367 파티(포드-폴커슨 알고리즘)

이번 문제는 파티에서 음식을 준비할 때, 음식의 종류와 할 수 있는 음식 종류, 그리고 가져올 수 있는 음식의 개수가 제한되어 있을 때, 최대한의 음식을 준비하는 것을 목표로 하는 내용입니다.

 

party

 

문제의 링크입니다.

https://www.acmicpc.net/problem/2367

2367번: 파티

이 문제를 풀기 위해서는 최대 유량 알고리즘을 알아야 합니다.  최대 유량은 제한 조건이 있을 때, 그 조건을 지키는 한도 내에서 최대의 결과를 얻을 때 사용됩니다.

 

최대유량과 관련되어서 설명한 곳은 다음 게시물을 참조하시길 바랍니다.

https://sdev.tistory.com/1352

[C/C++] 백준 #2316 도시 왕복하기 2(포드-폴커슨 알고리즘)

 

최대유량 알고리즘을 알고 있다고 해도, 이 문제를 어떻게 그래프로 만드는 가가 중요합니다.  저는 다음과 같은 그래프를 사용했습니다.

maximum flow graph

일단 소스는 0번 노드를 사용했습니다.  그리고 N명의 파티 참석자들은 1~N번 노드를 사용했습니다.  음식은 N+1번부터 N+D번을 사용했습니다.  마지막으로 싱크 노드는 N+D+1 노드를 사용했습니다.  주어진 K는 파티 참석자들이 가져갈 수 있는 음식의 개수이므로, 0번 노드에서 파티 참석자들 노드들로 최대 K까지 유량을 설정했습니다.  파티 참석자들과 음식들간의 관계는 모두 허용 유량 1인 간선으로 표현했습니다.  위 그림에서 빨간색 간선들은 모두 허용 유량 1인 간선들입니다.  음식 노드들과 싱크 노드들 사이에는 각각 음식들의 제한 개수들을 허용 용량으로 설정했습니다.

 

소스 노드에서 싱크 노드까지 도달하는데 있어서 허용 용량이 1인 빨간색 간선들을 반드시 지나므로 깊이 우선 탐색(DFS)를 사용했습니다.  깊이 우선 탐색이 구현하기 편리하고, 돌아올 때, 유량의 간선을 조절하면 편하기 때문에 굳이 너비 우선 탐색을 사용치 않았습니다.

 

제가 구현한 소스입니다.

//------------------------------------------------
//    baekjoon #2367
//        - by Aubrey Choi
//        - created at 2023-04-28
//------------------------------------------------
#include <cstdio>
#include <unordered_map>
using namespace std;

unordered_map<int, int> *adj;
int *visited;
bool dfs(int u, int e, int c)
{
    if(u == e) return true;
    visited[u] = c;
    for(auto v : adj[u])
    {
        if(v.second == 0 || visited[v.first] == c) continue;
        if(dfs(v.first, e, c))
        {
            adj[u][v.first] -= 1;
            adj[v.first][u] += 1;
            return true;
        }
    }
    return false;
}

int main()
{
    int n, k, d, s, t;
    scanf("%d%d%d", &n, &k, &d);
    adj = new unordered_map<int, int>[n+d+2];
    visited = new int[n+d+2];
    for(int i = 1; i <= n; i++)
    {
        adj[0][i] = k;
        adj[i][0] = 0;
    }
    for(int i = 1; i <= d; i++)
    {
        scanf("%d", &s);
        adj[n+i][n+d+1] = s;
        adj[n+d+1][n+i] = 0;
    }
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &s);
        for(int j = 0; j < s; j++)
        {
            scanf("%d", &t);
            adj[i][n+t] = 1;
            adj[n+t][i] = 0;
        }
    }
    int ans = 0;
    while(dfs(0, n+d+1, ans+1)) ans++;
    printf("%d\n", ans);
}