[C/C++] 백준 1671번 - 상어의 저녁식사

Algorithm/BOJ

[C/C++] 백준 1671번 - 상어의 저녁식사

poopooreum 2024. 4. 15. 09:40

✏️문제 링크

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

1671번: 상어의 저녁식사

어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크

www.acmicpc.net

✏️문제 설명

✏️문제 풀이

이분매칭으로 구현하는 문제이고 다만 조금은 생각을 해봐야하는 부분들이 있습니다.

일반적인 이분매칭은 그냥 입력받는 간선 정보를 그대로 이분 그래프로 구현하면 되는 반면, 이 문제는

상어들이 잡아먹을 수 있는 조건들이 있기 때문에 그 점들을 고려해야 합니다.

그래서 저는 아래와 같이 조건을 구성했습니다.

각 상어들을 A와 B라고 할 때

1. A의 사이즈, 속도, 지능이 B보다 모두 크다면 graph[a].push_back(b)

2. B의 사이즈, 속도, 지능이 A보다 모두 크다면 graph[b].push_back(a)

3. A의 사이즈, 속도, 지능이 B보다 모두 크다면 graph[a].push_back(b)

다만 여기서 samecount변수를 선언해서 모두 같은 경우를 세주었습니다. 비교문을 돌리는 횟수가 총 NC2인데

samecount가 nC2라면 한 마리가 다 잡아먹을 수 있기 때문에 그 경우에는 1을 출력하도록 하였습니다.

4. 위의 조건들이 다 아닐 때

이렇게 조건문을 이용해서 비교 후 그래프를 구현하였고 N-총 매칭수로 정답을 출력했습니다.

✏️문제 코드

/*
이분 매칭을 구현하되
각 상어들의 크기,지능,속도를
비교해서 그래프를 구현하자

그런다음 이분 매칭을 한 후
전체 상어수에서 총 매칭수를 빼자
*/
#include<iostream>
#include<vector>
#include<tuple>
using namespace std;
#define MAX 51
typedef tuple<long, long, long>edge;

int N;
long ssize, speed, intelligence;
vector<long>graph[MAX];
vector<edge>input;
long node[MAX];
bool visit[MAX];
bool dfs(int shark);
int findMax(edge node1, edge node2);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> ssize >> speed >> intelligence;
		input.push_back(edge(ssize, speed, intelligence));
	}

	long samecount = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			edge tmp = input[i];
			edge tmp2 = input[j];
			int check = findMax(tmp, tmp2);
			if (check == 1)
				graph[i+1].push_back(j+1);
			else if (check == -1)
				graph[j+1].push_back(i+1);
			else if (check == 100) {
				samecount++;
				graph[i+1].push_back(j+1);
			}
		}
	}

	int count = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 2; j++) {
			fill(visit, visit + MAX, false);
			if (dfs(i))
				count++;
		}
	}
	
	long res = N * (N - 1) / 2;
	if (samecount == res)
		cout << 1;
	else
		cout << N - count;
}

bool dfs(int shark)
{
	for (int i = 0; i < graph[shark].size(); i++) {
		int shark2 = graph[shark][i];
		if (visit[shark2])
			continue;
		visit[shark2] = true;
		if (node[shark2] == 0 || dfs(node[shark2])) {
			node[shark2] = shark;
			return true;
		}
	}
	return false;
}

int findMax(edge node1, edge node2) // node1이 더 크면 true를, node2가 더 크면 false를 반환
{
	long size1 = get<0>(node1);
	long speed1 = get<1>(node1);
	long intelligence1 = get<2>(node1);
	long size2 = get<0>(node2);
	long speed2 = get<1>(node2);
	long intelligence2 = get<2>(node2);

	if (size1 == size2 && speed1 == speed2 && intelligence1 == intelligence2)
		return 100;
	if (size1 >= size2 && speed1 >= speed2 && intelligence1 >= intelligence2)
		return 1;
	else if (size1 <= size2 && speed1 <= speed2 && intelligence1 <= intelligence2)
		return -1;
	return 0;
}