백준 1671번: 상어의 저녁식사 (C++)

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

1671번: 상어의 저녁식사

---

Level: Platinum III

Solved By: Bipartite Matching, Edmonds Karp

 

잡아먹는 상어와 잡아먹히는 상어들을 이분 그래프로 나누어줍니다. 여기서 제가 원하는 네트워크는 소스로부터 잡아먹는 상어들에게 capacity 2를 주며 연결하고(한 상어당 2개까지 먹을 수 있기 때문), 잡아먹는 상어들이 잡아먹히는 상어들을 잡아먹을 수 있다면 capcity 1의 간선을 연결해줍니다. 그리고, 상어는 한번 잡아먹히면 끝이기 때문에 잡아먹히는 상어들을 capacity 1의 간선으로 sink까지 연결해줍니다.

 

그리고, 유량을 흘려보내 주면 잡아먹히는 상어들의 최댓값을 구할 수 있습니다. 결론적으로 원하는 것은 남은 상어들의 최솟값이기 때문에 N - (최대 유량 값)을 구해주면 되겠습니다.

 

하지만, 여기서 반례가 존재합니다. N이 2개가 주어졌고, 그 2개가 서로 잡아먹을 수 있는 경우라면 어떻게 될까요

위처럼 주어진다면, 네트워크는 '서로 잡아먹는다'로 결론을 짓고, 최대 유량 값이 2가 되어 답은 0이 됩니다. 하지만, 먼저 잡아먹은 상어가 있다면 잡아먹힌 상어는 상대 상어를 잡아먹을 수 없다고 알려줘야 합니다. 저는 이를 해결하기 위해 2차원 배열 방문을 썼습니다.

for(int i = 1; i <= N; i++){
	for(int j = 1; j <= N; j++){
		if(i == j) continue;
		if(visited[i][j]) continue;
		if(compare(v[i], v[j]) == 1){
			addLine(i * 2, j * 2 + 1, 1);
			visited[j][i] = true;
		}
		else if(compare(v[i], v[j]) == 2){
			addLine(i * 2, j * 2 + 1, 1);
		}
	}
}

(+ compare함수의 반환 값이 1이면 서로 같다, 2면 더 크다라고 판단하게 작성했습니다.)

위 코드와 같이 자기 자신을 잡아먹을 수 없으니 당연히 continue 시키고, 만약 compare가 1이라면(능력치가 같다면), 간선을 추가해주되 for문을 돌면서 잡아먹히는 상어가 잡아먹는 상어의 입장이 되었을 때 불가능하다고 판단하게 하고 visited에 체크를 해주는 식으로 풀었습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#define MAX 104
#define INF 2e9
#define SOURCE 102
#define SINK 103
using namespace std;

int N;
vector<int> adj[MAX];
int c[MAX][MAX];
int f[MAX][MAX];
bool visited[MAX][MAX];

struct shark{
    int a, b, c;
};

int compare(shark A, shark B){
    if(A.a == B.a && A.b == B.b && A.c == B.c) return 1;
    if(A.a >= B.a && A.b >= B.b && A.c >= B.c) return 2;
    else return 3;
}

void addLine(int a, int b, int cap){
    adj[a].push_back(b);
    adj[b].push_back(a);
    c[a][b] = cap;
}

int edmondsKrap(int source, int sink){
    int ret = 0;
    while(true){
        int parent[MAX];
        memset(parent, -1, sizeof(parent));
        queue<int> q;
        q.push(source);
        
        while(!q.empty()){
            int now = q.front();
            q.pop();
            
            for(int i = 0; i < adj[now].size(); i++){
                int next = adj[now][i];
                
                if(c[now][next] - f[now][next] > 0 && parent[next] == -1){
                    parent[next] = now;
                    q.push(next);
                }
            }
        }
        
        if(parent[sink] == -1) break;
        
        int temp = INF;
        
        for(int i = sink; i != source; i = parent[i]){
            temp = min(temp, c[parent[i]][i] - f[parent[i]][i]);
        }
        
        for(int i = sink; i != source; i = parent[i]){
            f[parent[i]][i] += temp;
            f[i][parent[i]] -= temp;
        }
        
        ret += temp;
    }
    return ret;
}

int main(){
    cin >> N;
    vector<shark> v(N + 1);
    for(int i = 1; i <= N; i++){
        cin >> v[i].a >> v[i].b >> v[i].c;
    }
    
    // sink to from
    for(int i = 1; i <= N; i++){
        addLine(SOURCE, i * 2, 2);
    }
    
    // to to sink
    for(int i = 1; i <= N; i++){
        addLine(i * 2 + 1, SINK, 1);
    }
    
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            if(i == j) continue;
            if(visited[i][j]) continue;
            if(compare(v[i], v[j]) == 1){
                addLine(i * 2, j * 2 + 1, 1);
                visited[j][i] = true;
            }
            else if(compare(v[i], v[j]) == 2){
                addLine(i * 2, j * 2 + 1, 1);
            }
        }
    }
    int flow = edmondsKrap(SOURCE, SINK);
    
    cout << N - flow;
    return 0;
}