[백준] 1671. 상어의 저녁식사 + 벡터에 값을 입력하는 빠른 방법

문제

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

한 상어가 다른 상어를 잡아먹는 동안 나머지 상어들은 상어를 잡아먹을 수 없으며, 이미 잡아먹힌 상어는 다른 상어들을 잡아먹을 수 없다.

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

입력

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

출력

 

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

 

 

여러가지 상어가 서로 먹고 먹힙니다. 이때, 상어 A와 B의 스펙이 모두 같다면 서로를 잡아 먹을 수 있습니다.

따라서 만약 두 상어가 스펙이 모두 같다면 하나의 간선만 그을 수 있게 만들면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;

struct shark {
	int a, b, c;
};
int N, eat[51], v[51];
vector<shark>sharks;
vector<int>arr[51];
bool dfs(int k) {
	for (auto r : arr[k]) {
		if (v[r])continue;
		v[r] = 1;

		if (eat[r]==-1 || dfs(eat[r])) {
			eat[r] = k;
			return true;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	sharks.resize(N);

	for (auto& i : sharks)cin >> i.a >> i.b >> i.c;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (sharks[i].a == sharks[j].a &&
				sharks[i].b == sharks[j].b &&
				sharks[i].c == sharks[j].c) { //만약 서로 잡아먹을 수 있으면
				if (i > j)arr[i].push_back(j); //i가 j보다 인덱스가 크면 i가 잡아먹음
			}
			else if (sharks[i].a >= sharks[j].a &&
				sharks[i].b >= sharks[j].b &&
				sharks[i].c >= sharks[j].c) {
				arr[i].push_back(j); //i가 j를 잡아먹을 수 이씀
			}
		}
	}int cnt = N;
	memset(eat, -1, sizeof(eat));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 2; j++) {
			memset(v, 0, sizeof(v));
			if (dfs(i))cnt--;
		}
	}
	cout << cnt;
}

이분매칭을 이용해 두 그룹의 최대 매칭의 수를  구하면 됩니다.

인접 리스트를 사용했습니다.

vector<shark>sharks;
cin>>N;
sharks.resize(N);
for (auto& i : sharks)cin >> i.a >> i.b >> i.c;

이렇게 작성하면 모든 sharks에 대해 a,b,c를 입력할 수 있습니다.

 

다만 인덱스가 0부터 시작하기때문에....

 

dfs를 사용할때 eat배열을 1부터가 아닌 0부터 사용해야하므로 -1으로 memset을 해주어야합니다.