백준 1671번: 상어의 저녁식사 (C++)
https://www.acmicpc.net/problem/1671
1671번: 상어의 저녁식사
어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크
www.acmicpc.net
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;
}