algospot ARCTIC 남극 기지

문제

https://algospot.com/judge/problem/read/ARCTIC

걸린 시간

01 : 31 : 02

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int visited[100]; // 탐사기지

// 결정 문제 : bfs
bool decision(vector<pair<double, double>>& location, double gap){
    queue<pair<double, double>> q;
    q.push(make_pair(location[0].first, location[0].second));
    visited[0] = 1;
    while(!q.empty()){
        auto tmp = q.front();
        double curx = tmp.first;
        double cury = tmp.second;
        q.pop();
        for(int i = 0; i < location.size(); i++){
            if(!visited[i]){
                double nextx = location[i].first;
                double nexty = location[i].second;
                // 두 탐사기지 사이의 거리가 무전기 출력보다 작거나 같다면
                if(sqrt(pow(abs(curx-nextx), 2)+pow(abs(cury-nexty), 2)) <= gap){
                    visited[i] = 1;
                    q.push(make_pair(nextx, nexty));
                }
            }
        }
    }
    for(int i = 0; i < location.size(); i++)
        if(!visited[i])
            return false;
    return true;
}

// 최적화 문제
double optimize(vector<pair<double, double>>& location){
    double left = 0, right = 1001;
    for(int it = 0; it < 100; it++){
        double mid = (left+right)/2.0;
        memset(visited, 0, sizeof(visited));
        // 현재의 무전기 출력으로 모든 기지간에
        // 연락이 가능한가?
        if(decision(location, mid))
            right = mid;
        else
            left = mid;
    }
    return left;
}

int main(){
    int tc;
    scanf("%d", &tc);
    while(tc--){
        int n;
        scanf("%d", &n);
        double t1, t2; // tmp
        vector<pair<double, double>> location;
        for(int i = 0; i < n; i++){
            scanf("%lf %lf", &t1, &t2);
            location.push_back(make_pair(t1, t2));
        }
        printf("%.2lf\n", optimize(location));
    }
    return 0;
}

bfs 를 이용해 결정 문제를 구현하여 풀이하였다.