[BOJ4386] 별자리 만들기 (프림 알고리즘, 최소신장트리, MST)

 

 

---

문제 링크 

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

4386번: 별자리 만들기

 

문제 풀이

- 별자리(노드)를 모두 연결하는 최소 비용을 구하는 문제 

- 프림 알고리즘으로 풀이  (최소신장트리, MST)

- 시간 복잡도 : O(ElogV)

 

1) 2차원 좌표로 입력 주어지는데 각각 노드 1, 2, .. 로 보고 노드별 거리 값을 계산하여 컬렉션에 담는다 (양방향 그래프)

2) 시작 노드는 1로 고정해서 프림 알고리즘 수행 

- 방문한적 있으면 continue;

- 방문한적 없으면 visit 배열 체크, 이동 비용 합산, 우선 순위 큐에 연결된 다음 노드를 추가 

- 이때 우선 순위 큐는 cost 비용 오름차순 정렬 (최소힙, logV) 

3) 구한 결과값 출력 (소수점 둘째자리)

 

참고. 비슷한 문제 

https://dev-ljw1126.tistory.com/362

[BOJ1774] 우주신과의 교감 (그리디, 크루스칼, MST, 최소신장트리)

 

제출 코드

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

public class Main {
    
     static int n;

    static List<Edge>[] adj;

    static class Edge implements Comparable<Edge> {
        int idx;
        double cost;

        public Edge(int idx, double cost) {
            this.idx = idx;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge edge) {
            if(cost < edge.cost) return -1;
            else if(cost == edge.cost) return 0;
            return 1;
        }
    }

    static class Point {
        int num;
        double x;
        double y;

        public Point(int num, double x, double y) {
            this.num = num;
            this.x = x;
            this.y = y;
        }
    }

    static double distance(Point p1, Point p2) {
        double dx = Math.pow(p1.x - p2.x, 2);
        double dy = Math.pow(p1.y - p2.y, 2);
        return Math.sqrt(dx + dy);
    }
    
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        n = Integer.parseInt(br.readLine());
        
        // 각 인덱스를 별(노드) 번호로 함
        Point[] points = new Point[n + 1];
        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            double x = Double.parseDouble(st.nextToken());
            double y = Double.parseDouble(st.nextToken());

            points[i] = new Point(i, x, y);
        }

        adj = new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) adj[i] = new ArrayList<>();

        // 중복x, 별들 사이의 거리를 계산하여 인접행렬에 저장
        for(int i = 1; i <= n; i++) {
            for(int j = i + 1; j <= n; j++) {
                double distance = distance(points[i], points[j]);

                adj[i].add(new Edge(j, distance));
                adj[j].add(new Edge(i, distance));
            }
        }
    }

    // 프림 알고리즘 수행
    static void pro() {
        Queue<Edge> que = new PriorityQueue<>();
        que.add(new Edge(1, 0.0)); // 시작 노드는 1 고정

        boolean[] visit = new boolean[n + 1];

        double result = 0.0;
        while(!que.isEmpty()) {
            Edge cur = que.poll();

            if(visit[cur.idx]) continue;

            visit[cur.idx] = true;
            result += cur.cost;

            for(Edge next : adj[cur.idx]) {
                if(visit[next.idx]) continue;

                que.add(next);
            }
        }

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

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}