[백준문제풀이] 1671 상어의 저녁식사

 

풀이일시 : 2020-08-23

​

 

문제 :

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

능력치가 모두 같은 상어 A, B가 있다면 A가 B를, B가 A를 잡아먹을 수는 있지만 A, B가 서로 잡아먹을수는 없다.

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

​

 

입력:

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

ex)

5

4 5 5

10 10 8

5 7 10

8 7 7

8 10 3

​

 

출력:

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

ex)

2

​

 

풀이 :

살아남을 수 있는 상어 수의 최소값 = 상어:상어로 매칭이 최대한 많이 되게끔 하면된다.

dfs 와 이분매칭을 이용해 풀이해준다.

1. 크기 / 속도 / 지능을 비교하여 다른 상어에 비해 모든 능력치가 높다면 먹을 수 있다.

2. 한 상어가 두마리의 상어만 먹을 수 있다.

3. 서로 잡아먹기는 불가능

 

dbstndi6316.tistory.com/64

[기본문제풀이] DFS 깊이우선탐색

dbstndi6316.tistory.com/59

[기본문제풀이] bipartite matching

#include <iostream>
#include <vector>
#define MAX 1001
using namespace std;

vector<int> a[MAX];
int c[MAX];
int d[MAX];
int n;
int stat[MAX][3]; // 스탯을 저장할 배열이 필요하다.

bool dfs(int x) {
	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i];
		if (c[y])
			continue;
		c[y] = true;
		if (d[y] == 0 || dfs(d[y])) {
			d[y] = x;
			return true;
		}
	}
	return false;
}

int main() {
	scanf_s("%d", &n);
	for (int i = 1; i <= n; i++) {
		int a, b, c;
		scanf_s("%d %d %d", &stat[i][0], &stat[i][1], &stat[i][2]); //스탯을 입력해준다.
	}
	for (int i = 1; i <= n - 1; i++) { //1 2 3 4
		for (int j = i + 1; j <= n; j++) { // 2 3 4 5
			if (stat[i][0] == stat[j][0] && stat[i][1] == stat[j][1] && stat[i][2] == stat[j][2]) { //현재와 다음 상어의 스탯이 다 동일하면
				a[i].push_back(j); //i가 j 잡아먹음의 관계
			}
			//i와 j 관계는 이전 문제들로 생각해보면 
			//i가 j 일을할 수있다. 의 관계로 생각하면 된다. 아직 해결한건 아님. 잡아먹은거 아직아님
			else if (stat[i][0] >= stat[j][0] && stat[i][1] >= stat[j][1] && stat[i][2] >= stat[j][2]){
			a[i].push_back(j); //i가 j잡아먹은거
			}
			else if (stat[i][0] <= stat[j][0] && stat[i][1] <= stat[j][1] && stat[i][2] <= stat[j][2]){
			a[j].push_back(i); //j가 i잡아먹은거
			}
		}
	}
    //누가 누굴 잡아먹을수있는지 구했으니 이제 최대로 몇마리를 잡아먹을수있는지 구하자
	int count = 0;
	for (int k = 0; k < 2; k++) { //dfs를 두번돌리는 이유는? = 먹을수있는 최대 상어의 마릿수는 두마리
		for (int i = 1; i <= n; i++) {
			fill(c, c + MAX, false);
			if (dfs(i))
				count++; //죽는 상어 수
		}
	}
	printf("%d\n", n - count); //전체상어에서 죽는 상어 빼면 살아남은 상어수
	return 0;
}
​