[Algospot] 남극 기지 (문제 ID : ARCTIC)

문제

남극에는 N 개의 탐사 기지가 있습니다. 남극의 겨울은 혹독하기 때문에, 남극의 겨울이 찾아오면 탐사 기지들간의 왕래가 중단됩니다. 겨울에도 서로 통신하며 연구를 지속하기 위해, N 개의 무전기를 구입해 각 탐사 기지에 배치하려 합니다. 이 때, 두 탐사 기지 사이의 거리가 D 라고 하면, 무전기의 출력이 D 이상이어야만 통신이 가능합니다. 모든 탐사 기지에는 똑같은 무전기가 지급됩니다. 탐사 본부가 다른 모든 기지에 연락을 할 수 있기 위해 필요한 무전기의 최소 출력은 얼마일까요?

탐사 본부는 다른 기지를 통해 간접적으로 연락할 수 있다고 가정합니다.

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 기지의 수 N (<= 100)이 주어지고, 그 다음 줄에 2개씩의 실수로 각 기지의 좌표 (x,y) 가 주어집니다. 기지의 위치는 0 이상 1000 이하의 실수입니다. 이 때 첫 번째 주어지는 기지가 탐사 본부라고 가정합니다.

 

출력

각 테스트 케이스마다, 탐사 본부가 다른 모든 기지에 연락을 할 수 있기 위해 필요한 최소 무전기의 출력을 소숫점 밑 셋째 자리에서 반올림해 출력합니다.

---

마찬가지 최적화 결정 문제이다. 저번 DARPA 문제를 풀었더니 어느정도 정형화된 형식이 눈에 들어온다.

마찬가지로 optimize 함수를 통해 가능한 거리를 구하고,

decision을 통해 특정 거리에 대해 모든 레이더가 통신 가능한지 여부를 반환한다.

다만 이번 문제는 decision을 하기 위해 queue를 이용한 bfs기법을 사용했다.

bfs는 워낙 많이 풀어봤고 쉽기 때문에 큰 어려움이 없다. 그러나 계속 답이 안나와 실수한 부분은 기지 방문 여부인 visit 배열을 초기화 하는 문제때문이었다. visit는 decision이 실행될 때 마다 전부 false로 초기화가 되어야하는데, main에서 한 번만 초기화 했다 보니 이상한 답이 나오고 말았다. 주의하자.

이번 문제도 마찬가지로 소수점 둘째자리까지 출력해야하기 때문에 <iomanip>헤더를 포함해 부동소수점을 고정했다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/ARCTIC.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;

vector<pair<double, double>> base;
double dist[101][101];
int C, N;
bool visit[102];

bool decision(double d)
{
	for (int i = 0; i < 101; i++) visit[i] = false;
	visit[0] = true;
	queue<int> q;
	q.push(0);
	int count = 0;

	while (!q.empty()) {
		int here = q.front();
		q.pop();
		count++;
		for (int i = 0; i < N; i++) {
			if (!visit[i] && dist[here][i] <= d) {
				q.push(i);
				visit[i] = true;
			}
		}
	}
	return N == count;
}

double optimize()
{
	double lo = 0.0, hi = 1416.0;
	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()
{
	cin >> C;
	while (C--) {
		cin >> N;
		base.clear();

		for (int i = 0; i < N; i++) {
			double x, y;
			cin >> x >> y;
			base.push_back({ x,y });
		}

		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
			{
				pair<double, double> point1 = base[i];
				pair<double, double> point2 = base[j];
				dist[i][j] = sqrt((point2.first - point1.first) * (point2.first - point1.first) + (point2.second - point1.second) * (point2.second - point1.second));
			}

		cout << fixed << setprecision(2);
		cout << optimize() << endl;
	}
}