boj, 백준) 2191. 들쥐의 탈출 ( C / C++ )

1. 문제 링크

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

2191번: 들쥐의 탈출

2. 문제 개요

매에게 잡아먹히지 않기 위해 들쥐들은 땅굴로 도망가야 한다. 하지만 땅굴로 도망치는 속도가 있기 때문에 항상 모든 쥐들이 도망갈 수 있는 것은 아니다. 들쥐와 땅굴의 위치, 그리고 들쥐의 속도와 매가 도착하는 시간이 주어졌을 때, 잡아먹히게 되는 들쥐들의 최소수를 구하는 프로그램을 작성하자.

 

3. 문제 힌트

 들쥐와 땅굴을 이분그래프로 만든다.

 

4. 문제 풀기

거리 구하는 함수를 만들어 쥐와 모든 땅굴 간의 거리를 비교한다.

매가 도착하는 시간과, 쥐의 속도를 곱하여 움직일 수 있는 최대 거리를 구한다.

땅굴과 쥐와의 거리가 그 거리보다 짧은지 비교하여 매가 오기 전에 땅굴로 도착할 수 있다면 간선을 이어준다.

 

매칭 된 쥐와 땅굴은 숨을 수 있음을 나타내고, 최대로 숨을 수 있는 것이 먹히는 쥐를 최소한으로 구하는 것과 같다.

따라서 이분매칭을 해주고 나서 전체 쥐의 수에서 빼주도록 하자.

 

 

5. 코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, s, v;
pair<double, double> l[100];
vector<vector<int>> mouse;
bool visited[100] = { false };

int hiding[100];

double get_dist(pair<double, double> a, pair<double, double> b)
{
	return (b.first - a.first)*(b.first - a.first) + (b.second - a.second)*(b.second - a.second);
}

bool dfs(int cur)
{
	if (visited[cur])
		return false;

	visited[cur] = true;

	int len = mouse[cur].size();

	for (int i = 0; i < len; ++i)
	{
		int next = mouse[cur][i];

		if (hiding[next] == -1 || dfs(hiding[next]))
		{
			hiding[next] = cur;
			return true;
		}
	}
	return false;
}

int main()
{
	scanf("%d %d %d %d", &n, &m, &s, &v);
	double limit = (s * v)*(s * v);
	mouse.resize(n);
	fill(hiding, hiding + m, -1);


	for (int i = 0; i < n; ++i)
		scanf("%lf %lf", &l[i].first, &l[i].second);

	for (int i = 0; i < m; ++i)
	{
		pair<double, double>hole;
		scanf("%lf %lf", &hole.first, &hole.second);

		//compare mouse to hole
		for (int j = 0; j < n; ++j)
		{
			double dist = get_dist(l[j], hole);
			
			if (dist <= limit)
				mouse[j].push_back(i);
		}
	}
	int ans = 0;
	for (int i = 0; i < n; ++i)
	{
		fill(visited, visited + m, false);
		if (dfs(i))
			ans++;
	}
	printf("%d", n - ans);
	return 0;
}

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~