백준 1774 - 우주선과의 교감

문제

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

리뷰

크루스칼을 통해 풀이할 수 있는 문제였다.

좌표 정보를 저장하기 위해 Node, 간선 정보를 저장하기 위해 Edge 클래스를
정의하였다. 이후 우주선들의 좌표 정보를 입력받으며 저장하고, 우주선간의
연결 정보를 입력받으며 유니온 파인드 연산을 통해 분리집합을 형성해주었다.

이후, 우주선들로 좌표로부터 모든 가능한 간선들을 생성하여 간선 비용 기준
최소힙에 저장하고 크루스칼을 돌리며 MST를 형성하는 간선들의 비용이 합을
구하였다.

이 문제를 풀며 엄청 애먹었던 부분은 double 타입의 계산과 관련된 면이었다.
좌표간 거리를 계산하는 calcDist 메서드에서 그냥 int 타입의 값의 제곱으로
계산을 하였다가 정밀도 차이로 인해 4%대에서 계속 틀렸습니다를 마주하였다.
부동소수점 타입을 사용할 때 계산시 유의해야 한다는 점을 다시금 상기시킬 수 있는
문제였다.

로직의 시간복잡도는 간선의 개수가 $M=N(N-1)$일 때 크루스칼의 복잡도가
$O(MlogM)$으로 수렴하므로, $N=1,000$인 최악의 경우에도 무난히 제한 조건
2초를 통과한다.

코드

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

import static java.lang.Integer.parseInt;

public class Main {
    static int N;
    static int[] parent;
    static List<Node> ships = new ArrayList<>();
    static PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingDouble(e -> e.w));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());
        parent = new int[N + 1];

        int x, y;
        ships.add(null);
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            x = parseInt(st.nextToken());
            y = parseInt(st.nextToken());

            ships.add(new Node(i, x, y));
        }

        int u, v;
        Arrays.fill(parent, -1);
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());

            union(u, v);
        }

        double w;
        for (int i = 1; i < ships.size() - 1; i++) {
            u = ships.get(i).num;
            for (int j = i + 1; j < ships.size(); j++) {
                v = ships.get(j).num;

                if (u == v) continue;

                w = calcDist(ships.get(i), ships.get(j));
                pq.offer(new Edge(u, v, w));
            }
        }


        System.out.printf("%.2f\n", kruskal());
        br.close();
    }

    static double kruskal() {

        double sum = 0;

        while (!pq.isEmpty()) {
            Edge e = pq.poll();
            int r1 = find(e.u);
            int r2 = find(e.v);

            if (r1 == r2) continue;

            if (parent[r1] < parent[r2]) {
                parent[r1] += parent[r2];
                parent[r2] = r1;
            } else {
                parent[r2] += parent[r1];
                parent[r1] = r2;
            }

            sum += e.w;
        }

        return sum;
    }

    static double calcDist(Node n1, Node n2) {
        double val1 = Math.pow((n2.x - n1.x), 2);
        double val2 = Math.pow((n2.y - n1.y), 2);

        return Math.sqrt(val1 + val2);
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

        return parent[u] = find(parent[u]);
    }

    static void union(int u, int v) {
        int r1 = find(u);
        int r2 = find(v);

        if (r1 == r2) return;

        if (parent[r1] < parent[r2]) {
            parent[r1] += parent[r2];
            parent[r2] = r1;
        } else {
            parent[r2] += parent[r1];
            parent[r1] = r2;
        }
    }

    static class Node {
        int num, x, y;

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

    static class Edge {
        int u, v;
        double w;

        public Edge(int u, int v, double w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}

결과