문제
남극에는 n개의 탐사 기지가 있습니다. 남극의 겨울은 혹독하기 때문에, 겨울이 찾아오면 탐사 기지들 간의 왕래가 중단됩니다. 겨울에도 서로 통신하며 연구를 지속하기 위해, n개의 무전기를 구입해 각 탐사 기지에 배치해서 기지 간 연락망을 구축하려고 합니다.
모든 무전기의 통신 반경은 d이며, 두 탐사 기지는 사이의 거리가 d 이하여야만 서로 연락을 할 수 있습니다.
각 기지 간에는 다른 기지를 통해 간접적으로 연락할 수도 있지만, 항상 모든 기지 간에 서로 연락을 할 수 있어야 합니다.
통신 반경이 큰 무전기는 비싸기 때문에, 가능한 한 무전기의 통신 반경을 최소화하고 싶습니다. 어떻게 연락망을 구축해야 할까요? 각 기지의 위치가 주어질 때, 가능한 한 무전기의 최소 통신 반경을 계산하는 프로그램을 작성하세요.
시간 및 메모리 제한
프로그램은 1초 안에 실행되어야 하며, 64mb 이하의 메모리를 사용해야 합니다.
입력
입력의 첫 줄에는 테스트 케이스의 수 C가 주어집니다. 각 테스트 케이스의 첫 줄에는 기지의 수 n(1<=n<=100)이 주어지고, 그 다음 줄에 두 개씩의 실수로 각 기지의 좌표 (x, y)가 주어집니다. 기지의 위치는 0 이상 1000 이하의 실수입니다.
출력
각 테스트 케이스마다, 가능한 최소 통신 반경을 소숫점 밑 셋째 자리에서 반올림해 출력합니다.
풀이
이 문제는 많은 경우의 수 중에서 가장 좋은 답을 구하는 문제이므로 최적화 문제이다. 문제를 가장 처음 보고 든 생각은 minimun spanning tree를 이용해 문제를 풀 수 있지 않을까 하는 생각이었다.
하지만 이 문제는 edge의 전체 길이 합을 최소화하는 문제가 아니라, edge들 중 길이가 가장 큰 것의 값을 최소화하는 문제이기 때문에, mst 알고리즘을 그대로 적용할 수는 없었다.
그래서 최적화 문제를 결정 문제로 바꿔서 풀되, 그렇게 바뀐 결정 문제를 풀 때 mst와 비슷한 접근 방식을 사용해 보기로 했다.
최적화 문제를 결정 문제로 바꿔서 풀 때 이득을 얻을 수 있으려면, 결정 문제를 푸는 빠른 알고리즘이 존재해야 한다는 것이다. 기껏 최적화 문제를 결정 문제로 바꾸었는데 실행시간을 줄일 수 없으면 아무 의미가 없기 때문이다.
그래서 나는 "최소 통신 반경을 가지는 연락망을 구하는 문제"를 "x이하의 통신 반경을 가지는 연락망이 존재하는지의 여부를 구하는 문제"로 바꾼 후, 이 문제를 푸는 데 있어
mst를 구하는 prim algorithm과 비슷한 방식을 이용해 보았다. 기본적으로는 greedy algorithm인데, 우리가 만들어가고 있는 tree에 속하는 집합과 속하지 않는 집합을 나누어
매 순간 limit보다 짧은 거리에 있는 node를 택해 tree에 포함시키는 것이다.
static boolean decision(ArrayList<Pair<Double, Double>> curr, ArrayList<Pair<Double, Double>> recent, double limit) {
if(curr.size() == locations.size()) return true;
ArrayList<Pair<Double, Double>> newlyUpdated = new ArrayList<>();
for(int i = 0 ; i < recent.size() ; i++) {
for(int j = 0 ; j < locations.size() ; j++) {
if(recent.indexOf(locations.get(j)) >= 0) continue;
double x1 = recent.get(i).getKey();
double y1 = recent.get(i).getValue();
double x2 = locations.get(j).getKey();
double y2 = locations.get(j).getValue();
double distance = Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
if(distance <= limit) {
if(!newlyUpdated.contains(locations.get(j)) && !curr.contains(locations.get(j))) {
newlyUpdated.add(locations.get(j));
}
}
}
}
if(recent.size() == 0) newlyUpdated.add(locations.get(0));
else if(newlyUpdated.size() == 0) return false;
curr.addAll(newlyUpdated);
return decision(curr, newlyUpdated, limit);
}distance가 limit보다 작고 지금까지의 tree에 포함되지 않은 node들을 한 단계에 모두 포함시킨다. (prim algorithm에서는 최솟값 하나만을 포함시킨다.)
이 문제는 탐욕적 선택 속성을 만족하기 때문에 위 알고리즘은 올바르게 작동할 것이라고 예상할 수 있다.
그리고 이 결정 알고리즘을 이용하여 최적화 문제를 해결한다.
static double optimize() {
double lo = 0;
double hi = calcMaxDist();
for(int i = 0 ; i < 100 ; i++) {
double mid = (lo + hi) / 2.0;
if(decision(new ArrayList<>(), new ArrayList<>(), mid)) hi = mid;
else lo = mid;
}
return hi;
}decision 알고리즘의 time complexity는 O(n^2)으로 optimize 함수에서 이 함수를 100번 call하더라도 제한 시간 안에 충분히 문제를 풀 수 있다.
책에서는 결정 문제를 푸는 알고리즘으로 서로 거리가 d 이하인 기지들을 우선 전부 연결한 뒤, 이들이 하나로 연결되어 있는지 확인하는 방법을 제시한다.
어떤 그래프가 connected graph인지 확인하기 위해서 DFS 또는 BFS를 사용할 수 있는데, 이것 역시 time complexity는 O(n^2)으로, 내가 활용한 방법과 비슷한 실행 시간을 가질 것 같다.
예제 입력으로 프로그램을 실행해본 결과는 아래와 같다.
2
5
0 0
1 0
1 1
1 2
0 2
1.0
6
1.0 1.0
30.91 8
4.0 7.64
21.12 6.0
11.39 3.0
5.31 11.0
10.181989000190484
유념할 점
- 현재 배우고 있는 주제에만 얽매이지 말고, 이전까지 배웠던 방법들도 자유롭게 생각해보기
