백준 2191번: 들쥐의 탈출 (C++)

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

2191번: 들쥐의 탈출

---

Solved By: Bipartite Matching, Geometry

 

들쥐와 땅굴 관계라고 파악하여 각각의 좌표가 주어진 것으로 어떤 들쥐가 어떤 땅굴에 가기까지 걸리는 시간들을 구합니다.

이 시간들을 바탕으로 S 이하라면 들쥐가 땅굴에 들어갈 수 있다고 판단하여 인접 배열에 넣어줍니다.

이 인접 배열을 바탕으로 이분 매칭을 돌려서 결괏값을 도출할 수 있습니다.

 

#include <iostream>
#include <vector>
#include <memory.h>
#include <cmath>
#define MAX 201
#define pdd pair<double, double>
using namespace std;

vector<int> adj[MAX];
bool visited[MAX];
int occupy[MAX];
int n, m, s, v;

vector<pdd> a;
vector<pdd> b;

bool biMatch(int node){
    for(int i = 0; i < adj[node].size(); i++){
        int next = adj[node][i];
        
        if(visited[next]) continue;
        visited[next] = true;
        
        if(biMatch(occupy[next]) || occupy[next] == 0){
            occupy[next] = node;
            return true;
        }
    }
    
    return false;
}

double cal(int i, int j){
    double val = sqrt(pow(b[j].first - a[i].first, 2)
    + pow(b[j].second - a[i].second, 2));
    
    return val;
}

int main(){
    cin >> n >> m >> s >> v;
    for(int i = 0; i < n; i++){
        double q, r; cin >> q >> r;
        a.push_back({q, r});
    }
    
    for(int i = 0; i < m; i++){
        double q, r; cin >> q >> r;
        b.push_back({q, r});
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            //cout << cal(i, j) << '\n';
            if(cal(i, j) / (double)v <= s){
                adj[i + 1].push_back(j + 1);
            }
        }
    }
    
    int result = 0;
    for(int i = 1; i <= n; i++){
        memset(visited, false, sizeof(visited));
        if(biMatch(i)) result++;
    }
    
    cout << n - result;
    return 0;
}