[백준 2191] 들쥐의 탈출

[ghdcksgml1]

아이디어

매가 도착했을때 잡아먹히는 들쥐들의 수를 최소로 하기 위해서

각 구덩이에 들어갈 수 있는 들쥐가 1마리이므로, 이분매칭을 통해서 최대로 매칭한 후

(전체 들쥐의 수 - 매칭된 들쥐의 수) 를 통해 정답을 알아낸다.

들어갈 수 있는 구덩이를 구하는 방법은 피타고라스 공식을 이용해서 (x1, y1) , (x2,y2) 두 정점 사이의 거리를 구하고

그 거리가 S(매가 도착하는 시간(초)) * V(들쥐가 (초)당 움직이는 거리) 보다 작거나 같으면 간선을 추가해준다.

시간복잡도

O(MN²)

소스코드

// 언어 : C++ , (성공/실패) : 1/0 , 메모리 : 2168 KB , 시간 : 0ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h> // memset
#include <math.h>
#define MAX 101

using namespace std;

vector<int> a[MAX];
int d[MAX];
bool c[MAX];
int N,M;
float S,V;

pair<int,int> mouse[MAX];
pair<int,int> hole[MAX];

bool dfs(int x){
    for(auto t : a[x]){
        if(c[t]) continue;
        c[t] = true;
        if(d[t] == 0 || dfs(d[t])){
            d[t] = x;
            return true;
        }
    }
    return false;
}

int main(void){
    // 입출력 속도 최적화
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>N>>M>>S>>V;

    for(int i=1;i<=N;i++){
        float x,y; cin>>x>>y;
        mouse[i] = {x,y};
    }
    for(int i=1;i<=M;i++){
        float x,y; cin>>x>>y;
        hole[i] = {x,y};
    }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            float tmp = sqrt(pow(abs(mouse[i].first-hole[j].first),2) + pow(abs(mouse[i].second-hole[j].second),2));
            if(tmp <= S*V){
                a[i].push_back(j);
            }
        }
    }

    int count = 0;
    for(int i=1;i<=N;i++){
        fill(c,c+MAX,false);
        if(dfs(i)) count++;
    }

    cout<<N-count<<'\n';

    return 0;
}