💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에 네 정수 N, M, S, V가 주어진다. 다음 N개의 줄에는 들쥐의 x, y좌표가 주어지고, 그 다음 M개의 줄에는 땅굴의 x, y좌표가 주어진다. 모든 좌표는 절댓값이 1,000을 넘지 않는다.

🧺출력
첫째 줄에 잡아먹히게 되는 들쥐의 최솟값을 출력한다.

🔋예제 입출력

🔮예제 입력

2 2 5 10 
1.0 1.0 
2.0 2.0 
100.0 100.0 
20.0 20.0 

🔮예제 출력

1

💉문제 분석

🔋분류

최대유량, 네트워크유량, 이분매칭, 피타고라스의 정리

🔋난이도

플래티넘IV

💉문제 풀이

🔋해법

이 문제는 상어문제와 매우 유사합니다.

우선 새가 지상에 도착하는데 필요한 거리와 쥐와 땅굴사이의 거리를 비교하면 답을 유도할 수 있습니다.

먼저 쥐와 땅굴사이의 거리는 피타고라스의 정리를 통해 얻을 수 있구요,

만약에

쥐와 땅굴사이의 거리 <= 새가 지상에 도착하는데 필요한거리

라고했을때, 참이라면 i번째쥐는 땅굴로 들어가 새로부터 안전할것이구요,
거짓이라면 새한테 잡아먹히게 되겠죠.

답은 잡아먹히게 되는 쥐의 수이지만,
우리가 이분매칭을 통해 얻을 수 있는 정보는 살아난쥐의 수와 어떤쥐가 어떤 굴로 들어갔는지를 알 수 있습니다.

다음과 같을때, 아래와 같은 식이 성립합니다.

답 = 잡아먹히게 되는 쥐의 수 = 전체 쥐의 수 - 살아난 쥐의 수

따라서 답은 "N - (이분매칭이 참을 내뱉은수)"가 되겠습니다.

🔋소스코드

#include <bits/stdc++.h>

constexpr int INF = 987654321;
constexpr int MAX = 101;

std::pair<float, float> mouse[MAX], cave[MAX];
std::vector<float> adj[MAX];
bool visit[MAX];
int d[MAX];

float pitagoras(std::pair<float, float>& a, std::pair<float, float>& b) {
	int x = (a.first - b.first);
	int y = (a.second - b.second);
	return std::sqrt(x * x + y * y);
}

bool bfs(int start) {
	for (int i = 0; i < adj[start].size(); ++i) {
		int x = adj[start][i];

		if (visit[x]) continue;
		visit[x] = true;

		if (d[x] == 0 || bfs(d[x])) {
			d[x] = start;
			return true;
		}
	}
	return false;
}

int main() {
	int N, M, S, V;
	std::cin >> N >> M >> S >> V;

	for (int i = 1; i <= N; ++i) std::cin >> mouse[i].first >> mouse[i].second;
	for (int i = 1; i <= M; ++i) std::cin >> cave[i].first >> cave[i].second;

	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= M; ++j) {
			if (pitagoras(mouse[i], cave[j]) <= (float)(S * V)) {
				adj[i].push_back(j);
			}
		}
	}

	int result = 0;
	for (int i = 1; i <= N; ++i) {
		std::fill(visit, visit + MAX, false);
		if (bfs(i)) ++result;
	}
	std::cout << N - result;
}

이번 문제는 재미있었습니다.
굳굳~!

💉마치며...

궁금한 부분있으시면 댓글로 질문주세요~