[BOJ/Java] 3628. Knockdown

🌍💥 [BOJ/Java] 3628. Knockdown 💣🔥

🔗 문제 링크

📌 3628번 - Knockdown

---

📖 문제 해석

이 문제는 전 세계를 파괴하기 위해 특정 지점에 폭탄을 배치하는 시나리오를 다룬다. 💀💣
각 폭탄은 동일한 파괴 반경을 가지며, 전 세계를 파괴할 수 있는 최소한의 반경을 찾아야 한다. 🌍➡️💥

지구는 반지름이 1인 단위 구(Sphere) 로 모델링되며, 폭탄의 위치는 위도(latitude, φ)와 경도(longitude, λ) 로 주어진다.
거리는 구면 거리(Spherical Distance) 로 측정된다. 🌐📏

---

🧐 풀이 과정

1️⃣ 구 좌표 변환 (위도/경도 → 3D 좌표) 🗺️➡️🛸

지구는 구형이므로, 주어진 위도와 경도를 3D 좌표계로 변환해야 한다.

위도(φ)와 경도(λ)를 사용하여 다음 공식을 이용한다.

x = cos(φ) * cos(λ)  
y = cos(φ) * sin(λ)  
z = sin(φ)

 

이제 각 폭탄은 3D 공간의 점(Point) 으로 변환된다. 🏔️🌍

---

2️⃣ 최소 반경을 찾기 위한 접근 방식 🔍🎯

목표는 어느 지점에서든 가장 가까운 폭탄까지의 거리가 최소 반경 r 이하가 되도록 하는 것이다.

즉, 지구상의 모든 점이 어떤 폭탄과도 최대 r 거리 이내에 있도록 보장해야 한다.
이를 해결하기 위해, 이분 탐색(이진 탐색) + 기하학적 계산을 활용한다. ⚙️🧮

🔹 고려해야 할 후보 점들

1. 각 폭탄의 반대편 점 (Antipodal Point)
   • 폭탄이 위치한 점의 정반대 지점이 유력한 후보가 된다.
   • 이는 (−x,−y,−z)(-x, -y, -z) 로 쉽게 구할 수 있다.
2. 두 폭탄 사이의 중간점 (Pairwise Midpoint)
   • 두 개의 폭탄이 있다면, 이들의 중간 벡터 방향이 적절한 후보가 될 수 있다.
3. 세 폭탄으로 이루어진 정점 (Triple-wise Normal Vector)
   • 세 개의 폭탄이 형성하는 평면의 법선 벡터가 유력한 후보가 된다.

🔹 최적화 목표: min max(dot product)

 

각 후보 지점에서 모든 폭탄과의 최대 내적(dot product) 값을 최소화하는 p를 찾아야 한다.
이 값이 작을수록 최적의 반경이 줄어든다.

최소 반경은 acos(최적의 내적 값) 으로 계산된다.

r = arccos(min max(p · bomb_i))

---

💻 코드 구현 (Java)

import java.io.*;
import java.util.*;

public class Main {
    static final double EPS = 1e-9;  // 오차 허용 범위

    // 3차원 좌표를 저장하는 클래스
    static class Point {
        double x, y, z;
        Point(double x, double y, double z) {
            this.x = x; this.y = y; this.z = z;
        }
        Point add(Point p) { return new Point(x + p.x, y + p.y, z + p.z); }
        Point subtract(Point p) { return new Point(x - p.x, y - p.y, z - p.z); }
        Point multiply(double s) { return new Point(x * s, y * s, z * s); }
        double dot(Point p) { return x * p.x + y * p.y + z * p.z; }  // 내적
        Point cross(Point p) {  // 외적
            return new Point(y * p.z - z * p.y,
                             z * p.x - x * p.z,
                             x * p.y - y * p.x);
        }
        double norm() { return Math.sqrt(x * x + y * y + z * z); }  // 벡터 크기
        Point normalize() {  // 단위 벡터 변환
            double n = norm();
            if(n < EPS) return new Point(0, 0, 0);
            return new Point(x / n, y / n, z / n);
        }
    }

    static double candidateValue(Point p, Point[] bombs) {
        double val = -1e9;
        for (Point b : bombs) {
            val = Math.max(val, p.dot(b));
        }
        return val;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int n = Integer.parseInt(br.readLine().trim());
        Point[] bombs = new Point[n];

        for (int i = 0; i < n; i++) {
            String[] parts = br.readLine().trim().split("\\s+");
            double lat = Math.toRadians(Double.parseDouble(parts[0]));
            double lon = Math.toRadians(Double.parseDouble(parts[1]));
            double cosLat = Math.cos(lat);
            bombs[i] = new Point(cosLat * Math.cos(lon), cosLat * Math.sin(lon), Math.sin(lat));
        }

        double best = 1e9;

        for (int i = 0; i < n; i++) {
            Point cand = new Point(-bombs[i].x, -bombs[i].y, -bombs[i].z);
            best = Math.min(best, candidateValue(cand, bombs));
        }

        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                Point sum = bombs[i].add(bombs[j]);
                if (sum.norm() > EPS) {
                    best = Math.min(best, candidateValue(sum.multiply(-1).normalize(), bombs));
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = j+1; k < n; k++) {
                    Point cross = bombs[i].subtract(bombs[j]).cross(bombs[i].subtract(bombs[k]));
                    if (cross.norm() > EPS) {
                        best = Math.min(best, candidateValue(cross.normalize(), bombs));
                        best = Math.min(best, candidateValue(cross.multiply(-1).normalize(), bombs));
                    }
                }
            }
        }

        best = Math.max(-1, Math.min(1, best));
        double ans = Math.acos(best);
        out.printf("%.6f\n", ans);
        out.flush();
    }
}

---

⏳ 시간 복잡도 분석

• 각 폭탄마다 후보 탐색 → O(n)
• 두 개의 폭탄을 이용한 후보 탐색 → O(n^2)
• 세 개의 폭탄을 이용한 후보 탐색 → O(n^3)
• 최대 폭탄 개수 n=20n = 20 이므로 최악의 경우 O(8000), 충분히 실행 가능 ✅

---

💡 느낀 점

✅ 구면 기하학과 이분 탐색을 조합한 흥미로운 문제였다! 🌍✨
✅ 폭탄이 최소한으로 커버해야 할 범위를 찾는 과정이 기하학적으로 재미있었다. 🎯🔥
✅ 벡터 연산(내적, 외적, 단위 벡터 변환) 의 중요성을 다시 한번 체감했다! 🚀