BOJ 1671 상어의 저녁식사

57:10
처음에는 이분매칭의 in과 out에서 아이디어를 얻었다.
상어 a에 대하여 상어 a가 안 먹혔으면 in[a] = -1(초기값),
먹혔으면 in[a] = (상어 a를 먹은 상어의 번호)를 저장한다. 그런데 사실 여기서 out은 필요 없다.
그래서 사실 이분매칭에서 아이디어를 얻었지만 이분매칭은 사용하지 않았다.

상어를 최대한 많이 먹어야 하므로 상어를 바로 먹게 하지말고 찜(?)만 하도록 하자.
상어 a가 먹을 수 있는 상어들 중 하나를 상어 b라고 하자.
싱어 b가 아직 누군가에게 찜 된 적이 없으면 그냥 상어 a가 b를 찜한다.
하지만 상어 b가 이미 찜된 상태라면 b를 찜한 상어를 상어 c라고 할 때, c가 b 말고 다른 상어를 찜하도록 유도한다. 상어 c가 다른 상어를 찜할 수 있다면 상어 b는 상어 a의 차지가 된다.

dfs(x) : (상어 x가 다른 상어들한테 양보를 요구하면서라도 상어를 하나 찜할 수 있는가)
라고 생각하고 함수를 작성한다.

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define f first
#define s second
#define x first
#define y second
#define all(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ti3 = tuple<int, int, int>;

struct sharkInfo {
    int size, speed, intel;
    sharkInfo(int pm1, int pm2, int pm3) : size(pm1), speed(pm2), intel(pm3) {}

    bool operator <=(sharkInfo other) const {
        return (size <= other.size) && (speed <= other.speed) && (intel <= other.intel);
    }
    bool operator >=(sharkInfo other) const {
        if(size == other.size && speed == other.speed && intel == other.intel) return false;
        return (size >= other.size) && (speed >= other.speed) && (intel >= other.intel);
    }
};

int N;
vector<sharkInfo> sharks;
vector<int> g[50];
bool visited[50];
int in[50]; // out[50];

bool dfs(int here) {
    if(visited[here]) return false;
    visited[here] = true;
    for(int there : g[here]) {
    	// there 상어가 이미 찜된 상태라면 in[there] 상어가 there 상어 말고 다른 상어를 찜하도록 유도한다.
        if(in[there] != -1 && !dfs(in[there])) continue;
        // in[there] 상어가 다른 상어를 찜해줬다면, there 상어는 here 상어의 차지다.
        in[there] = here;
        return true;
    }
    return false;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    memset(in, -1, sizeof in);

    cin >> N;
    for(int i=0; i<N; i++) {
        int a,b,c; cin >> a >> b >> c;
        sharks.emplace_back(a,b,c);
    }
    for(int i=0; i<N; i++) {
        for(int j=i+1; j<N; j++) {
            if(sharks[i] <= sharks[j]) g[j].emplace_back(i);
            if(sharks[i] >= sharks[j]) g[i].emplace_back(j);
        }
    }

    int ans = 0;
    for(int i=0; i<N; i++) {
        memset(visited, 0, sizeof visited);
        ans += dfs(i);
        memset(visited, 0, sizeof visited);
        ans += dfs(i);
    }
    cout << N - ans << '\n';

    return 0;
}