[백준]4386: 별자리 만들기 - JAVA

[백준]4386: 별자리 만들기

www.acmicpc.net/problem/4386

4386번: 별자리 만들기

풀이

별들의 좌표를 간선으로 이었을때 최소인 비용을 찾는 문제로 MST알고리즘을 사용하여 풀면 된다.

 

별을 입력받을때 해당 별의 번호와 좌표를 저장해 주었다.

 

이 문제에서는 별들이 연결된 간선의 정보가 없으므로 모든 별들 사이의 거리를 직접 구하여 간선list에 저장해 주었다. 그다음 MST알고리즘인 prim, kruskal알고리즘을 사용하여 각각의 MST를 구해주면 된다.

 

코드

• prim 알고리즘

import java.util.*;
 
public class Main {
    
    static ArrayList<Node> startList = new ArrayList<>();
    static ArrayList<Edge>[] edgeList; 
    static boolean[] visited;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        int n = scan.nextInt();
        edgeList = new ArrayList[n];
        for(int i = 0; i < n; i++) {
            double x = scan.nextDouble();
            double y = scan.nextDouble();
            startList.add(new Node(i, x, y));
            edgeList[i] = new ArrayList<>();
        }
        
        //모든 간선 계산
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                double dist = Math.sqrt(Math.pow(startList.get(i).x - startList.get(j).x, 2) + Math.pow(startList.get(i).y - startList.get(j).y, 2));
                edgeList[i].add(new Edge(j, dist));
                edgeList[j].add(new Edge(i, dist));
            }
        }
        
        visited = new boolean[startList.size()];
        double result = prim();
        System.out.printf("%.2f", result);
    }
    
    public static double prim() {
        PriorityQueue<Edge> q = new PriorityQueue<>();
        q.offer(new Edge(0, 0));
        double dist = 0;
        
        while(!q.isEmpty()) {
            Edge current = q.poll();
            
            if(visited[current.end] == false) {
                dist += current.cost;
                visited[current.end] = true;
            }
            else continue;        
            
            for(int i = 0; i < edgeList[current.end].size(); i++) {
                Edge next = edgeList[current.end].get(i);
                if(visited[next.end] == false) q.offer(new Edge(next.end, next.cost));
            }
        }
        return dist;
    }
    
    public static class Node {
        int num;
        double x;
        double y;
        
        public Node(int num, double x, double y) {
            this.num = num;
            this.x = x;
            this.y = y;
        }
    }
    
    public static class Edge implements Comparable<Edge> {
        int end;
        double cost;
        
        public Edge(int end, double cost) {
            this.end = end;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Edge e) {
            if(this.cost < e.cost) return -1;
            return 1;
        }
    }
}
 

 

• kruskal 알고리즘

import java.util.*;
 
public class Main {
    
    static ArrayList<Node> startList = new ArrayList<>();
    static ArrayList<Edge> edgeList = new ArrayList<>(); 
    static int[] parent;
    static PriorityQueue<Edge> q = new PriorityQueue<>();
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        int n = scan.nextInt();
        for(int i = 0; i < n; i++) {
            double x = scan.nextDouble();
            double y = scan.nextDouble();
            startList.add(new Node(i, x, y));
        }
        
        //모든 간선 계산
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                double dist = Math.sqrt(Math.pow(startList.get(i).x - startList.get(j).x, 2) + Math.pow(startList.get(i).y - startList.get(j).y, 2));
                q.add(new Edge(i, j, dist));
            }
        }
        
        parent = new int[startList.size()];
        double result = kruskal();
        System.out.printf("%.2f", result);
    }
    
    public static double kruskal() {
        for(int i = 0; i < startList.size(); i++) {
            parent[i] = i;
        }
        
        double dist = 0;
        while(!q.isEmpty()) {
            Edge current = q.poll();
            
            int p1 = find(current.start);
            int p2 = find(current.end);
            
            if(p1 != p2) {
                union(p1, p2);
                dist += current.cost;
            }
        }
        return dist;
    }
    
    public static int find(int a) {
        if(parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }
    
    public static void union(int a, int b) {
        parent[a] = b;
    }
    
    public static class Node {
        int num;
        double x;
        double y;
        
        public Node(int num, double x, double y) {
            this.num = num;
            this.x = x;
            this.y = y;
        }
    }
    
    public static class Edge implements Comparable<Edge> {
        int start;
        int end;
        double cost;
        
        public Edge(int start, int end, double cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Edge e) {
            if(this.cost < e.cost) return -1;
            return 1;
        }
    }
}