[C/C++] 백준 #2188 축사 배정(이분 매핑)

#2188 문제는 이분 매핑의 대표적인 문제입니다.  이분 매핑(binary mapping)이라는 것은 최대 유량 알고리즘(maximum flow algorithm)의 특별한 버전입니다.

 

문제의 링크입니다.

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

2188번: 축사 배정

문제에서 축사를 소에 배정을 해주는데, 소들은 자신들이 원하는 축사들 중 하나를 배정받지 않으면 다른 축사에 들어가지 않으려 합니다.

이럴 경우 가능한 많은 소를 원하는 축사에 배정하는 알고리즘입니다.

 

이것을 푸는 알고리즘으로는 이분매핑(binary mapping)을 사용했습니다.

일단 처음 소부터 원하는 축사에 배정을 합니다.  만약 원하는 축사가 다른 소에 이미 배정되어있다면, 그 소가 다른 축사에 배정받을 수 있는지 검사합니다.  이 검사과정은 깊이우선탐색(DFS; Depth First Search)을 통하여 이루어집니다.  왜냐하면, 그 다른 축사를 검사할 때, 또다른 소가 이미 배정받아있을 수 있기 때문입니다.  이 과정을 거치면, 가능한 수의 소들이 원하는 축사를 배정받게 됩니다.

 

소와 축사

위 그림에서 첫번째 소는 첫번째 축사를 배정받습니다.

두번째 소는 첫번째 축사를 배정하려고 하니, 첫번째 축사는 이미 배정이 되었습니다.  이 때, 그냥 돌아가는 것이 아니고, 첫번째 축사를 배정받은 소가 다른 축사로 들어갈 수 있는지 검색을 합니다.  그래서 비어있는 축사가 있으면 그쪽으로 배정을 바꿉니다.  위 그림에서는 두번째 축사가 비어있으니, 첫번째 소는 그곳을 배정받게 되면 첫번째 축사는 비어있게 됩니다.  그 비어있는 축사를 두번째 소가 배정받습니다.

세번째 소는 세번째 축사가 비어있으므로 그곳을 배정합니다.

이렇게 하면 최대 축사배정의 수는 3개가 됩니다.

 

이 알고리즘을 작성한 소스는 다음과 같습니다.

//----------------------------------------------------------
//    baekjoon #2188 - Assign Cows at Barns
//        - by Aubrey Choi
//        - created at 2020-01-24
//----------------------------------------------------------
#include <stdio.h>
#include <memory.h>
#include <vector>

std::vector<int> adj[201];
int n, m, f[201], v[201];
bool check(int s, int p)
{
    v[s]=p;
    for(auto k:adj[s])
    {
        if(f[k] && (v[f[k]]==p || !check(f[k],p))) continue;
        f[k]=s;
        return true;
    }
    return false;
}
int getmaxflow()
{
    int i, r=0;
    for(i=1;i<=n;i++)
        if(check(i,i)) r++;
    return r;
}
int main()
{
    int s, t, i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&t);
        while(t--) { scanf("%d",&s); adj[i].push_back(s); }
    }
    printf("%d\n", getmaxflow());
}

 

v[] 배열은 방문을 했는지 아닌지를 나타냅니다.  매번 v[] 배열을 초기화하기가 싫어서, 여기서는 추가 변수를 두어서 배열초기화를 하지않고서 방문 표시를 하도록 했습니다.

f[] 배열은 해당 축사에 배정된 소입니다.