백준) 1671-상어의 저녁식사

문제 링크 : https://www.acmicpc.net/problem/1671

1671번: 상어의 저녁식사

문제

어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크거나 같다면 상어 A는 상어 B를 먹을 수 있다. 그러나, 상어들의 왕 김재홍은 상어들이 많이 없어지는 것을 방지하기 위해서 한 상어가 최대 두 개의 상어만 먹을 수 있게 했다. 상어들은 김재홍의 말을 모두 듣는다.

N마리 상어의 크기, 속도, 지능이 주어졌을 때, 살아남을 수 있는 상어의 최솟값을 구하시오.

입력

첫째 줄에 상어의 마리 수 N이 주어진다. 이 값은 50보다 작거나 같은 자연수이다. 둘째 줄부터 각 상어의 크기, 속도, 지능의 정보가 주어진다. 이 값은 2,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 살아남을 수 있는 상어의 최솟값을 출력한다.

풀이>>

네트워크 플로우 알고리즘 중 하나인 이분 매칭 알고리즘을 이용하여 풀이하였다. 뭔가 그래프 이론 심화 버전으로 갈수록 알고리즘 의존도가 높아지는 것 같다. 상어 들은 3가지 조건에 충족해야 다른 상어들을 잡아먹을 수 있다. 

이문제에서 요구하는 답은 최대로 살아남을 수 있는 상어의 수다. 그러므로  서열이 A >  B >  C  인 상어들이 있다고 해 보자    A 인 상어가  B를 먼저 먹지 않고 C를 잡아먹는  일은 일어나지 않는다는 것이다.  이분 매칭 알고리즘을 이용하여 상어들이 먹을 수 있는 최대의 개수를 구해준 후 전체 N - ans를 해주면 살아남을 수 있는 상어의 최소 수 가  만들어진다.

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
 
vector<int > a[51];
 
 
struct shark {
    int vol, vel , intel;
        //크기  속도   지능
};
 
shark stat[51];
 
int N;
 
int d[51];
int visited[51];
 
int dfs(int x)
{
    int i ;
 
    for( i = 0 ; i < a[x].size() ; i++  ) {
        int y = a[x][i];
 
        if(visited[y] ) continue;
 
        visited[y] = 1 ;
 
 
        if(d[y] == 0 || dfs(d[y])  ) {
 
            d[y] =x;
            return 1;
        }
 
    }
 
    return 0;
}
 
int main()
{
    int i,j;
    cin >> N; 
 
    for(i=1; i<= N ; i++) {
        cin >> stat[i].vol >> stat[i].vel >> stat[i].intel ;
    }
 
    for(i=1; i<=N-1 ;i++) {
 
                for(j=i+1;j<=N; j++) {
 
                    if(stat[i].vol == stat[j].vol && stat[i].vel == stat[j].vel && stat[i].intel == stat[j].intel  )
                        a[i].push_back(j);
                
                    else     if(stat[i].vol >= stat[j].vol && stat[i].vel >= stat[j].vel && stat[i].intel >= stat[j].intel  )
                        a[i].push_back(j);
                
                    else  if(stat[i].vol <= stat[j].vol && stat[i].vel <= stat[j].vel && stat[i].intel <= stat[j].intel  )
                        a[j].push_back(i);
 
                }
 
    }
 
int ans = 0 ;
int n=2;
 
    while(n--)
    for( i=1 ; i<=N ;i++)    {
 
        memset(visited,0,sizeof(visited));
        if(dfs(i)) ans++;
 
    }
 
cout << N-ans;
 
 
    return 0;
}