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

✏️문제 링크

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

1671번: 상어의 저녁식사

 

✏️문제 설명

 

 

✏️문제 풀이

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

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

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

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

각 상어들을 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;
}

 

 

✏️다른 이분 매칭 문제 보기

https://pooreumjung.tistory.com/339

[C/C++] 백준 열혈강호 문제 모음 / 백준 11375번, 백준 11376번

https://pooreumjung.tistory.com/340

[C/C++] 백준 2188번 - 축사 배정

https://pooreumjung.tistory.com/345

[C/C++] 백준 1298번 - 노트북의 주인을 찾아서