백준 4386 자바 - 별자리 만들기 (BOJ 4386 JAVA)

문제 : boj4386

 

 

1.

  모든 별을 이어야하고, 최소 비용을 구해야 한다. 따라서 N개의 정점(별)에 대해 이은 간선이 N-1개(모든 정점을 포함하려면 최소 N-1개의 간선이 필요하고, 최소비용을 위해서는 거기서 하나라도 간선이 추가되선 안되므로) 이어야만 모든 별을 이으면서 최소 비용이 가능하다. 따라서 Spanning Tree를 구성해야 하고, 최소 비용이어야 하므로 MST (Minimum Spanning Tree)를 구하는 문제임을 알 수 있다.

 

  후보군이 될 간선은 N개에 대해 다른 N-1개 모두로의 간선이므로 간선은 총 N*(N-1)개 존재할 수 있다. 이 중 N-1개를 골라 MST를 만들었을 때의 최소 비용이 답이다.

 

 

2.

  대표적인 MST 알고리즘에는 Prim과 Kruscal이 있다. 이 문제의 경우 N도 작고, 간선 개수도 작으므로 둘 중 뭘 써도 상관없다(시간복잡도로만 보면 정점이 적고 간선이 많을 땐 프림, 간선이 적을 땐 크루스칼이 효율적이다.). 별다른 응용 없이 기본 형태의 프림과 크루스칼 모두 바로 적용이 가능하다. 내 경우엔 프림과 크루스칼로 각각 짜봤다. 둘 다 제일 중요한건 N-1개의 간선만 만들기 위해서 사이클이 생기면 안된다는 점이다. 프림은 이걸 방문배열로 체크하고, 크루스칼은 Union-find로 체크한다.

 

 

코드1 (프림) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Edge {
    int b;
    double dist;
    public Edge(int b, double dist) {
        this.b = b;
        this.dist = dist;
    }
}

public class Main {
    private double getDist(double x1, double y1, double x2, double y2) {
        return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        double[][] arr = new double[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Double.parseDouble(st.nextToken());
            arr[i][1] = Double.parseDouble(st.nextToken());
        }

        ArrayList<Edge>[] edges = new ArrayList[n];
        for (int i = 0; i < n; i++) edges[i] = new ArrayList<>();

        for (int i = 0; i < n-1; i++) {
            for (int j = i + 1; j < n; j++) {
                double dist = getDist(arr[i][0], arr[i][1], arr[j][0], arr[j][1]);
                edges[i].add(new Edge(j, dist));
                edges[j].add(new Edge(i, dist));
            }
        }

        PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                if (o1.dist > o2.dist) return 1;
                else if (o1.dist < o2.dist) return -1;
                return 0;
            }
        });
        boolean[] v = new boolean[n];
        pq.add(new Edge(0, 0.0));

        double answer = 0.0;
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            if (v[cur.b]) continue;
            v[cur.b] = true;
            answer += cur.dist;

            for (Edge next : edges[cur.b]) {
                if (!v[next.b]) {
                    pq.add(next);
                }
            }
        }

        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

코드2 (크루스칼) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Edge {
    int a, b;
    double dist;
    public Edge(int a, int b, double dist) {
        this.a = a;
        this.b = b;
        this.dist = dist;
    }
}

public class Main {
    private int[] parents;

    private int find(int a) {
        if (parents[a] < 0) return a;
        return parents[a] = find(parents[a]);
    }

    private boolean union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;

        int h = parents[a] < parents[b] ? a : b;
        int l = parents[a] < parents[b] ? b : a;
        parents[h] += parents[l];
        parents[l] = h;
        return true;
    }

    private double getDist(double x1, double y1, double x2, double y2) {
        return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        double[][] arr = new double[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Double.parseDouble(st.nextToken());
            arr[i][1] = Double.parseDouble(st.nextToken());
        }

        ArrayList<Edge> edges = new ArrayList<>();

        for (int i = 0; i < n-1; i++) {
            for (int j = i + 1; j < n; j++) {
                double dist = getDist(arr[i][0], arr[i][1], arr[j][0], arr[j][1]);
                edges.add(new Edge(i, j, dist));
            }
        }

        Collections.sort(edges, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                if (o1.dist > o2.dist) return 1;
                else if (o1.dist < o2.dist) return -1;
                return 0;
            }
        });

        parents = new int[n];
        Arrays.fill(parents, -1);

        double answer = 0.0;
        for (int i = 0; i < edges.size(); i++) {
            Edge cur = edges.get(i);
            if (union(cur.a, cur.b)) {
                answer += cur.dist;
            }
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}