[ARCTIC] 문제 😄😄😄😄😄
남극에는 N 개의 탐사 기지가 있습니다. 남극의 겨울은 혹독하기 때문에, 남극의 겨울이 찾아오면 탐사 기지들간의 왕래가 중단됩니다. 겨울에도 서로 통신하며 연구를 지속하기 위해, N 개의 무전기를 구입해 각 탐사 기지에 배치하려 합니다. 이 때, 두 탐사 기지 사이의 거리가 D 라고 하면, 무전기의 출력이 D 이상이어야만 통신이 가능합니다. 모든 탐사 기지에는 똑같은 무전기가 지급됩니다. 탐사 본부가 다른 모든 기지에 연락을 할 수 있기 위해 필요한 무전기의 최소 출력은 얼마일까요?
탐사 본부는 다른 기지를 통해 간접적으로 연락할 수 있다고 가정합니다.
[풀이]
DARPA 와 같은 방법으로 decision() 으로 가능 한지 안한지를 확인한 후 optimize로 최소 반경을 구한다.
하나 문제를 잘 못 이해했던점이 있었는데, d 거리로 각 기지에서 모든 기지에 다이렉트로 연결해야만 하는 줄 알았는데
1번 기지에서 2번 기지에 연결하고 1번에서 3번 기지에 거리가 되지 않아도 2번과 3번 이 연결 가능하다면 간접적으로 연결 가능하다는 점이다.
입력
입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 기지의 수 N (<= 100)이 주어지고, 그 다음 줄에 2개씩의 실수로 각 기지의 좌표 (x,y) 가 주어집니다. 기지의 위치는 0 이상 1000 이하의 실수입니다. 이 때 첫 번째 주어지는 기지가 탐사 본부라고 가정합니다.
출력
각 테스트 케이스마다, 탐사 본부가 다른 모든 기지에 연락을 할 수 있기 위해 필요한 최소 무전기의 출력을 소숫점 밑 셋째 자리에서 반올림해 출력합니다.
입력 예제
2
5
0 0
1 0
1 1
1 2
0 2
6
1.0 1.0
30.91 8
4.0 7.64
21.12 6.0
11.39 3.0
5.31 11.0
출력 예제
1.00
10.18
전체 코드는 다음과 같습니다.
//
// ARCTIC.cpp
// AALGGO
//
// Created by inhyeok on 2021/11/04.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <utility>
#include <cmath>
#include <queue>
#include <cstring>
using namespace std;
ifstream fin("ARCTIC.txt");
int n;
double distances[101][101];
bool decision(double d){
// 방문했던곳들 표시
vector<bool> visited(n,false);
visited[0]= true;
// 방문했던 곳중 다른 곳으로 연결 가능한 곳을 찾기위해 q를 사용.
queue<int> q;
// 처음 0번 방문
q.push(0);
int seen =0;
// 더이상 연결 할 곳이 없을떄 까지
while(!q.empty()){
int here = q.front();
q.pop();
seen++;
for(int there=0; there<n; there++){
// 방문하지 않았고 거리내에 연결 가능 하다면.
if(!visited[there] && (distances[here][there] <= d)){
q.push(there);
visited[there] = true;
}
}
}
// d 거리로 모든 기지를 연결 할 수 있었다면.
return seen == n;
}
double optimize(){
double lo = 0, hi = 1415; // root 2000000 = 1414.213---
for(int i = 0; i<100; i++){
double mid = (lo + hi)/2.0;
if(decision(mid)){
hi = mid;
}
else{
lo = mid;
}
}
return hi;
}
int main(){
int test_case;
fin >> test_case;
for(int test=0; test < test_case; test++){
memset(distances,0,sizeof(distances));
fin >> n;
vector<pair<double, double> > locations;
for(int i = 0; i<n; i++){
double y,x;
fin >> y >> x;
locations.push_back(make_pair(y,x));
}
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
pair<double, double> f = locations[i];
pair<double, double> s = locations[j];
// 거리공식 사용
distances[i][j] = sqrt(pow(f.first-s.first,2) + pow(f.second-s.second,2));
}
}
// 대칭
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
distances[j][i] = distances[i][j];
}
}
printf("%.2f\n",optimize());
}
}
Comments