b4386. 별자리 만들기

 

https://www.acmicpc.net/problem/4386

 

 

 

✨ 자바로 푸는 별자리 만들기 문제 풀이

 

---

 

📌 문제 개요

 

백준 4386번 “별자리 만들기”는

주어진 N개의 별 좌표를 기반으로 별자리를 만들 때,

모든 별을 연결하면서 최소한의 선분 길이 합을 구하는 문제입니다.

 

즉, 모든 별을 잇되 최소 비용으로 연결하는 구조를 요구하며, 이는 전형적인 최소 신장 트리(MST, Minimum Spanning Tree) 문제입니다.

 

---

 

💡 예제 입력

3
1.0 1.0
2.0 2.0
2.0 4.0

 

예제 출력

3.41

 

---

 

🛠 알고리즘 접근 방식

 

별들 간 거리를 간선으로 보고,

이 중에서 가장 적은 거리의 간선들만을 선택해 모든 별을 연결해야 합니다.

 

이를 위해 프림 알고리즘을 사용합니다.

(크루스칼도 가능하지만, 이 코드는 프림 기반으로 작성됨)

 

 

✅ 핵심 아이디어

 

• 모든 별 사이의 거리(간선 비용)를 getDistance()로 계산
• dis[]: 현재까지 선택된 노드들과의 거리 중 최소값 저장
• isVisited[]: 이미 연결된 별인지 여부
• 가장 가까운 노드를 선택하면서 MST 구성

 

---

 

🧾 코드 해설

 

 

🧭 입력 및 초기화

N = Integer.parseInt(br.readLine());
stars = new double[N][2];
isVisited = new boolean[N];
dis = new double[N];

for (int i = 0; i < N; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    stars[i][0] = Double.parseDouble(st.nextToken());
    stars[i][1] = Double.parseDouble(st.nextToken());
    dis[i] = DOUBLE_MAX;
}
dis[0] = 0; // 0번 별에서 시작

 

🌠 프림 알고리즘 핵심 로직

for (int i = 0; i < N; i++) {
    int u = -1;
    double min = Double.MAX_VALUE;

    // 방문하지 않은 정점 중 가장 가까운 정점 선택
    for (int j = 0; j < N; j++) {
        if (!isVisited[j] && dis[j] < min) {
            min = dis[j];
            u = j;
        }
    }

    isVisited[u] = true;
    answer += dis[u];

    // u를 기준으로 다른 별과 거리 갱신
    for (int v = 0; v < N; v++) {
        if (!isVisited[v]) {
            dis[v] = Math.min(dis[v], getDistance(u, v));
        }
    }
}

 

📐 거리 계산 함수

private static double getDistance(int i, int j) {
    return Math.sqrt(Math.pow(stars[i][0] - stars[j][0], 2)
                   + Math.pow(stars[i][1] - stars[j][1], 2));
}

 

🎯 출력 처리

System.out.println(String.format("%.2f", answer));

 

---

 

✅ 핵심 포인트 정리

 

• MST를 요구하는 문제 → 프림 알고리즘 선택
• 모든 별 사이 거리는 실수(double) 연산 → sqrt, pow 사용
• String.format("%.2f", ...)을 통해 소수점 둘째 자리까지 출력

 

---

 

🌌 결론: 우주 속 별을 가장 효율적으로 잇기

 

이 문제는 좌표 기반의 최소 연결 비용을 묻는 대표적인 MST 문제로,

거리 계산과 정점 선택의 효율을 모두 고려해야 합니다.

 

🌟 별을 잇는 것은 낭만이지만, 알고리즘은 냉정하다.

프림 알고리즘은 가장 가까운 것부터 신중하게 이어간다.