baekjoon

[백준] 2191 들쥐의 탈출

윤만석 2023. 4. 26. 13:47

문제

N(1 ≤ N ≤ 100)마리의 들쥐들과 M(1 ≤ M ≤ 100)개의 땅굴이 있다. 각각의 들쥐는 2차원 평면상의 한 위치에 있고, 각각의 땅굴들도 2차원 평면상의 한 점에 위치한다.

들쥐들을 잡아먹는 매가 들쥐들을 습격했을 때, 쥐들은 매를 피하기 위해서 땅굴 속으로 숨을 수 있다. 모든 쥐들이 땅굴에 숨을 수 있다면 매에 잡아먹히는 쥐가 한 마리도 없겠지만, 각각의 땅굴에는 한 마리의 쥐만 들어갈 수 있을뿐더러 매가 도착하는 시간과 쥐들이 땅굴로 도망치는 속도가 있기 때문에 항상 모든 쥐들이 도망갈 수 있는 것은 아니다.

매는 현재를 기준으로 S(1 ≤ S ≤ 100)초가 지난 후에 지상에 도착한다. 각각의 들쥐들은 매 초당 V(1 ≤ V ≤ 100)만큼의 거리를 움직인다(즉 V가 쥐들의 초속이다). 만약 S초가 되기 전에 들쥐가 땅굴에 도착하게 되면 그 들쥐는 땅굴로 숨을 수 있다. 단, 들쥐가 도착하는 시간이 정확히 S인 경우에도 그 들쥐는 도망칠 수 있는 것으로 간주한다.

들쥐들은 종족 전체의 번영을 위해, 매에 잡아먹히게 되는 들쥐의 수가 최소가 되도록 도망치기로 하였다. 들쥐와 땅굴의 위치, 그리고 들쥐의 속도와 매가 도착하는 시간이 주어졌을 때, 잡아먹히게 되는 들쥐의 최소수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 네 정수 N, M, S, V가 주어진다. 다음 N개의 줄에는 들쥐의 x, y좌표가 주어지고, 그 다음 M개의 줄에는 땅굴의 x, y좌표가 주어진다. 모든 좌표는 절댓값이 1,000을 넘지 않는 실수이며 소숫점 셋째자리까지 주어질 수 있다.

출력

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

 

들쥐와 땅굴은 각각 1대1으로 매칭이 되어야 합니다.

이분그래프에서 매칭하는 이분매칭문제입니다.

만약 어떤 들쥐가 S*V거리 내에 땅굴에 들어갈 수 있으면 도망칠 수 있습니다.

모든 들쥐에 대해 각각 시간 내에 들어갈 수 있는 땅굴을 저장하고,

이분매칭을 수행합니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1}, INF = 987654321;

using namespace std;

int N, M, S, V;
float x, y;

struct obj {
	int x;
	int y;
};
int R, H, d[101], v[101];
obj rats[101];
obj holes[101];
vi adj[101];
float dist(obj a, obj b) {
	return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
bool dfs(int n) {
	if (v[n])return false;
	v[n] = 1;
	for (int r : adj[n]) {
		if (!d[r] || dfs(d[r])) {
			d[r] = n;
			return true;
		}
	}
	return false;
}
int main() {
	FAST;
	cin >> N >> M >> S >> V;
	REP(i, N) {
		cin >> x >> y;
		obj rat = {x,y};
		rats[++R]=rat;
	}
	REP(i, M) {
		cin >> x >> y;
		obj hole = {x,y};
		holes[++H] = hole;
	}
	REP(i, N) {
		REP(j, M) {
			if (dist(rats[i], holes[j]) <= S * V) {
				adj[i].push_back(j);
			}
		}
	}
	int cnt = 0;
	REP(i, N) {
		mset(v);
		if (dfs(i))cnt++;;
	}
	cout << N - cnt;
}

'baekjoon' 카테고리의 다른 글

[백준] 1915 가장 큰 정사각형  (0) 2023.04.28
[백준] 2240 자두나무  (0) 2023.04.28
[백준] 2310 어드벤처 게임  (0) 2023.04.26
[백준] 2251 물통  (0) 2023.04.26
[백준] 13913 숨바꼭질 4  (1) 2023.04.25