Foot Print

Recent Updates

See 27 more →

Foot Print

1671 상어의 저녁식사

6 min read

Link

상어의 저녁식사

Detail

1차풀이

풀이 과정

  1. 상어끼리의 포식관계를 탐색해서 그래프를 생성한다. O(N ^ 2)
  2. Source에서 최상위 포식자들을 찾아서 2만큼의 용량을 가진 간선을 연결한다. O(N)
  3. 최하위 상어를 찾아 SInk와 연결해준다.
  4. 최대유량을 흘려 보내준 다음. N - 최대유량이 남아있을 상어의 최솟값이다. (최악의 경우 O(N ^ 3)) N ⇐ 50이므로 가능할 것으로 보인다.

반례

4 4 3 8 4 3 8 4 3 8 4 3 8 해당 사례가 위 풀이의 반례를 가진다. 바로 2-3번과정에서 어떤 노드를 Sink, Source와 연결할 지 알 수 없는 것. 따라서 같은 상어에 대해서 노드가 두개가 생성되어야 했다.

2차풀이

풀이 과정

  1. 각 상어마다 2개의 노드를 만든다. 하나는 먹히는경우, 하나는 먹는 경우.

  2. 먹히는 경우의 노드에 Sink를 연결하고, 먹는 경우의 노드에 Source를 연결하여 Maximum Flow Problem으로 문제 영역을 옮긴다. (이때 두 그룹으로 명백하게 나뉘어지기 때문에 Bipartite Matching을 사용하여도 좋다.) 이 풀이를 보고도 실행하지 않은건 두가지 의문점이 남아있었기 때문이다.

  3. 1→2, 2→3, 3→1방식으로 잡아먹힌다면, “이미 먹힌상어는 다른상어를 먹을 수 없다”는 모순을 어떻게 해결하고 한마리만 남는다고 계산될까?

    1. 가정이 잘못되었다. 기본적으로 내부 데이터로 대소를 비교해야만 하기 때문에 저런 순환 케이스는 나올 수 없다.

  4. 순환이 되지 않는다면, 누가 어떻게 먹든 그 순서를 위상정렬하여 실현 가능함을 증명할 수 있다.

Error

4 4 8 9 4 8 9 4 8 9 4 8 9 서로가 서로를 먹을 수 있다보니 그냥 그대로 짜면 순환문제가 발생한다. 둘 중 한마리가 먹을수 있는 일방적 관계로 제한하니 문제가 해결되었다.

Code

#include<iostream>
#include<cmath>
#include<queue>
#include<algorithm>
#include<stack>
#include<array>
#include<vector>
#include<set>
 
#define LL long long
#define DEBUG true
#define PRINT_LINE std::cout << "--------------------" << '\n'
#define REPEAT(n) for(int _ = 0; _ < n; _++)
#define FAST_IO std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr)
 
#define MAX 102
#define ADD_TO_BE_FOOD 50
#define SOURCE 100
#define SINK 101
 
int graph[MAX][MAX];
int flow[MAX][MAX];
std::set<int> adj[MAX];
 
int from[MAX];
 
struct shark_information {
    int size;
    int speed;
    int intelligence;
};
 
bool operator>(const shark_information& eater, const shark_information& food) {
    bool big_size = eater.size >= food.size;
    bool high_speed = eater.speed >= food.speed;
    bool high_intel = eater.intelligence >= food.intelligence;
 
    return big_size and high_speed and high_intel;
}
 
bool operator==(const shark_information& a, const shark_information& b) {
    return a.size == b.size and a.speed == b.speed and a.intelligence == b.intelligence;
}
 
bool operator>=(const shark_information& a, const shark_information& b) {
    return a > b or a == b;
}
 
void create_graph(std::vector<shark_information> infos) {
    for(int i = 0; i < infos.size(); i++) {
        for(int j = i + 1; j < infos.size(); j++) {
            int eater, food;
            if(infos[i] >= infos[j]) {
                eater = i;
                food = j + ADD_TO_BE_FOOD;
            }
            else if(infos[j] > infos[i]){
                eater = j;
                food = i + ADD_TO_BE_FOOD;
            }
            else continue;
 
            graph[eater][food] = 1;
            adj[eater].insert(food);
            adj[food].insert(eater);
        }
    }
 
    for(int i = 0; i < infos.size(); i++) {
        //connect source
        adj[SOURCE].insert(i);
        adj[i].insert(SOURCE);
 
        graph[SOURCE][i] = 2;
 
        //connect with sink
        int j = i +ADD_TO_BE_FOOD;
        adj[SINK].insert(j);
        adj[j].insert(SINK);
 
        graph[j][SINK] = 1;
    }
}
 
bool bfs(int start, int dest, int& total_flow) {
    for(int& i : from) i = -1;
 
    std::queue<int> q;
 
    q.push(start);
    from[start] = start;
    while(not q.empty()) {
        int cur = q.front(); q.pop();
 
        for(auto next : adj[cur]) {
            if(from[next] != -1) continue;
            if(flow[cur][next] >= graph[cur][next]) continue;
 
            from[next] = cur;
            q.push(next);
 
            if(next == dest) goto FLOW_WATER;
        }
    }
 
    FLOW_WATER:
    if(from[dest] == -1) return false;
 
    int flow_value = INT32_MAX;
    for(int i = dest; i != start; i = from[i]) {
        flow_value = std::min(flow_value, graph[from[i]][i] - flow[from[i]][i]);
    }
 
    for(int i = dest; i != start; i = from[i]) {
        flow[from[i]][i] += flow_value;
        flow[i][from[i]] -= flow_value;
    }
 
    total_flow += flow_value;
    return true;
}
 
int get_maximum_flow() {
    int ret = 0;
    while(true) {
        if(not bfs(SOURCE, SINK, ret)) break;
    }
 
    return ret;
}
 
void print_graph(int start) {
    bool visited[MAX] = {false};
 
    std::queue<int> q;
    q.push(start);
    visited[start] = true;
 
    while(not q.empty()) {
        int cur = q.front();
        q.pop();
 
        for(auto next : adj[cur]) {
            if(visited[next]) continue;
            if(graph[cur][next] == 0) continue;
 
            visited[next] = true;
            q.push(next);
 
            std::cout << cur << ' ' << next << ' ' << graph[cur][next] << ' ' << flow[cur][next] << '\n';
        }
    }
}
 
int main() {
    FAST_IO;
    int n; std::cin >> n;
 
    std::vector<shark_information> infos(n);
    for(auto &info : infos) {
        std::cin >> info.size >> info.speed >> info.intelligence;
    }
 
    create_graph(infos);
    int max_flow = get_maximum_flow();
 
    std::cout << n - max_flow << std::endl;
 
//    print_graph(SOURCE);
}

Graph View