boj 1671 - 상어의 저녁식사

개요

이분매칭 문제가 아닌 것 같은데 이분매칭 알고리즘입니다. 사실 알고리즘 종류를 모르고 시작한다면 시간이 꽤나 소요될 것 같은 유형의 문제였습니다.

 

 상어의 크기, 속도, 지능이 주어질 때 상어 A의 세 가지 값이 상어 B의 세 가지 값보다 모두 크거나 같다면 A는 B를 먹을 수 있습니다. 여기서 잡아먹는 상어를 $V_L$에 두고 잡아먹히는 상어를 $V_R$에 두면 됩니다. 

 

 한 가지 예외는 상어 A의 모든 값이 상어 B와 동일한 경우입니다. 이 때는 단순하게 index를 기준으로 누가 누구를 잡아먹을 수 있을지 마음대로 정하면 됩니다. 왜냐하면 우리는 누가 살아남는지 관심이 있는 것이 아니라 최소로 생존할 수 있는 상어의 수에 관심이 있기 때문이죠.

 

 마찬가지로 이런 의문이 들 수도 합니다. "상어 A > B > C > D 가 있을 때, 상어 A가 B와 C를 먼저 먹으면 D가 살아남는 것 아냐?" 하지만 문제에서는 어느 경우의 수에서라도 최소로 생존 가능한 상어의 수를 구하는 것이기 때문에 위와 같은 케이스를 고려할 필요가 없습니다.

 

예제 1

 백준의 예제를 살펴봅시다!

5
4 5 5
10 10 8
5 7 10
8 7 7
8 10 3

 

위를 그래프로 나타내면 다음과 같습니다.

 

 최대 이분 매칭 알고리즘을 돌려보면 다음과 같습니다 (이분 매칭이 가능한 방법은 유일하지 않습니다. 하지만 최대 값이 3임은 확실합니다). 한 상어는 최대 2마리까지 먹을 수 있으므로 2번의 dfs를 돌려야 합니다.

 

 결과적으로 1, 4, 5는 먹혔고, 2와 3만 생존할 수 있게 되어 2마리가 남습니다. (전체 상어 수 5 - 최대 매칭 3 = 2)

 

 

예제 2

 한 예제만 더 살펴봅시다.

4
4 3 8
4 3 8
4 3 8
4 3 8

 

이 예제의 4마리 상어는 모두 동일한 수치를 갖고 있습니다. 따라서 단순히 index에 따라서 우열 관계를 추가해줍니다.

 

그러면 다음과 같이 그릴 수 있고, 

 

이분 매칭 결과 (유일하지 않음)는 아래와 같이 3이 되어서 1마리만 생존함을 알 수 있습니다.

코드

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;

int arr[51][3];
int N;

vector<int> graph[51];
int back[51];
char visited[51];
int dfs(int node){
        if(visited[node]) return 0;
        visited[node] = 1;

        int size = graph[node].size();
        for(int i=0; i<size; i++){
                int next = graph[node][i];
                if(!back[next] || back[next] != node && dfs(back[next])){
                        back[next] = node;
                        return 1;
                }
        }
        return 0;
}
int main(){
        scanf("%d",&N);

        for(int i=1; i<=N; i++)
                scanf("%d %d %d",&arr[i][0], &arr[i][1], &arr[i][2]);

        for(int i=1; i<=N; i++){
                for(int j=1; j<=N; j++){
                        if(i==j) continue;
                        if(arr[i][0] == arr[j][0] && arr[i][1] == arr[j][1] && arr[i][2] == arr[j][2]){
                                graph[i>j? j:i].push_back(i>j? i: j);
                                continue;
                        }
                        if(arr[i][0] >= arr[j][0] && arr[i][1] >= arr[j][1] && arr[i][2] >= arr[j][2])
                                graph[i].push_back(j);
                }
        }
        int Ans = 0;
        for(int i=1; i<=N; i++){
                memset(visited, 0, N+1);
                dfs(i);
                memset(visited, 0, N+1);
                dfs(i);
        }
        for(int i=1; i<=N; i++){
                if(back[i]) Ans++;
        }
        printf("%d\n",N-Ans);
}