백준 4722 - Underground Cables

문제

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

리뷰

크루스칼로 풀이할 수 있는 간단한 문제였다.

도시들의 정보가 x,y 꼴의 좌표로 주어지고 이 도시들을 최소한의 비용으로
이을 수 있는 MST의 총 비용을 구하는 것이 문제의 조건이었다.

우선 좌표 정보를 저장할 수 있는 Point 클래스와, 간선 정보를 저장할
Edge 클래스를 산정하였다. 이후 도시들의 좌표 정보를 입력받고 각 도시간의
간선을 설정하며 비용 기준 최소힙에 간선들을 저장하였다.

이후, 크루스칼에서 저장된 간선들을 바탕으로 MST를 형성하며 비용 합을 구해
답을 도출했다.

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

코드

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

import static java.lang.Integer.*;

public class Main {
    static int[] parent;
    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;
        int N, x, y;

        List<Point> points = new ArrayList<>();
        List<Double> answer = new ArrayList<>();

        while (true) {
            N = parseInt(br.readLine());
            if (N == 0) break;

            parent = new int[N];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                x = parseInt(st.nextToken());
                y = parseInt(st.nextToken());
                points.add(new Point(x, y));
            }

            for (int u = 0; u < points.size() - 1; u++)
                for (int v = u + 1; v < points.size(); v++)
                    pq.offer(new Edge(u, v, getDist(points.get(u), points.get(v))));

            answer.add(kruskal(N));
            points.clear();
            pq.clear();
        }

        for (Double ans : answer) {
            System.out.printf("%.2f\n", ans);
        }

        br.close();
    }

    static double getDist(Point p1, Point p2) {
        return Math.sqrt(Math.pow(p2.x - p1.x, 2) + Math.pow(p2.y - p1.y, 2));
    }

    static double kruskal(int N) {
        Arrays.fill(parent, -1);
        int selected = 0;
        double sum = 0;

        while (!pq.isEmpty() && selected < N - 1) {
            Edge e = pq.poll();

            if (!union(e.u, e.v)) continue;

            selected++;
            sum += e.w;
        }

        return selected == N - 1 ? sum : -1;
    }

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

        if (r1 == r2) return false;

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

        return true;
    }

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

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

    static class Point {
        int x, y;

        public Point(int x, int y) {
            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;
        }
    }
}

결과