[BOJ] 4386.별자리 만들기(MST,KRUSKAL, PRIM).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

MST 기본(?) 문제다.

가중치가 주어지지 않지만,

두 점 사이의 거리를 구하는 공식만 알고 있다면 쉽게 풀 수 있다.

Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2))

하지만 나는 바보... 처럼 정말 티 안나는 작은 오타 하나 때문에...

엄청난 오답을 보았다..

요즘들어 실수가 많은데,

침착하게 풀고, 문제가 발생하면 로직도 확인해야하지만

오타도 한 번 꼼꼼하게 확인해보자..!

#. Code_Kruskal

가능한 모든 간선을 확인해야해서

prim 보다 kruskal 이 상대적으로 더 빠른 속도를 보였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class BOJ4386 {
    
    static int N, parents[];
    static Point[] stars;
    static ArrayList<Edge> edgeList;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        stars = new Point[N];
        edgeList = new ArrayList<>();
        // 별 위치 저장
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            double x = Double.parseDouble(st.nextToken());
            double y = Double.parseDouble(st.nextToken());
            
            stars[i] = new Point(x, y);
        }
        // 별들간의 거리 저장
        for (int i = 0; i < N; i++) {
            Point now = stars[i];
            
            for (int j = i + 1; j < N; j++) {
                Point next = stars[j];
                
                // Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2))
                double dist = Math.sqrt(Math.pow(next.x - now.x, 2) 
                        + Math.pow(next.y - now.y, 2));
                
                edgeList.add(new Edge(i, j, dist));
            }
        }
        
        System.out.printf("%.2f", Prim());
    }
 
    private static double Prim() {
                
        edgeList.sort(null);
        
        parents = new int[N];
        make();
        
        double res = 0.0;
        int cnt = 0;
        for (Edge edge : edgeList) {
            if(union(edge.from, edge.to)) {
                res += edge.dist;
                if(++cnt == N - 1) return res;
            }
        }
        
        return res;
    }
    
    private static boolean union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        if(aRoot == bRoot) return false;
        parents[bRoot] = aRoot;
        return true;
    }
 
    private static int find(int n) {
        if(n == parents[n]) return n;
        return parents[n] = find(parents[n]);
    }
 
    private static void make() {
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
        
    }
 
    static class Point {
        double x, y;
 
        public Point(double x, double y) {
            super();
            this.x = x;
            this.y = y;
        }
        
    }
 
    static class Edge implements Comparable<Edge>{
        int from, to;
        double dist;
        
        public Edge(int from, int to, double dist) {
            super();
            this.from = from;
            this.to = to;
            this.dist = dist;
        }
 
        @Override
        public int compareTo(Edge o) {
            return Double.compare(this.dist, o.dist);
        }
    }
 
}
 

#. Code_prim

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class BOJ4386 {
    
    static int N;
    static Point[] stars;
    static ArrayList<Node>[] adj;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        stars = new Point[N];
        adj = new ArrayList[N];
        // 별 위치 저장.
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            double x = Double.parseDouble(st.nextToken());
            double y = Double.parseDouble(st.nextToken());
            
            stars[i] = new Point(x, y);
            adj[i] = new ArrayList<>();
        }
        // 별들간의 거리 저장
        for (int i = 0; i < N; i++) {
            Point now = stars[i];
            
            for (int j = i + 1; j < N; j++) {
                Point next = stars[j];
                
                // Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2))
                double dist = Math.sqrt(Math.pow(next.x - now.x, 2) 
                        + Math.pow(next.y - now.y, 2));
                
                adj[i].add(new Node(j, dist));
                adj[j].add(new Node(i, dist));
            }
        }
        
        System.out.printf("%.2f", Prim());
    }
 
    private static double Prim() {
        double res = 0.0;
        int cnt = 0;
        
        boolean visited[] = new boolean[N];
        PriorityQueue<Node>    pq = new PriorityQueue<>();
        // 0번 별부터 출발
        pq.add(new Node(0, 0));
        
        while(!pq.isEmpty()) {
            
            Node now = pq.poll();
            // 이미 방문한 별이라면 pass
            if(visited[now.idx]) continue;
            
            res += now.dist;
            visited[now.idx] = true;
            // 모든 별을 확인했다면 return
            if(++cnt == N) return res;
            
            for (Node next : adj[now.idx]) {
                // 이미 방문한 별이라면 pass
                if(visited[next.idx]) continue;
                
                pq.add(next);
            }
        }
        
        return res;
    }
 
    static class Point {
        double x, y;
 
        public Point(double x, double y) {
            super();
            this.x = x;
            this.y = y;
        }
        
    }
 
    static class Node implements Comparable<Node>{
        int idx;
        double dist;
        
        public Node(int idx, double dist) {
            this.idx = idx;
            this.dist = dist;
        }
 
        @Override
        public int compareTo(Node o) {
            return Double.compare(this.dist, o.dist);
        }
    }
}