백준 10021 - Watering the Fields

문제

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

리뷰

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

좌표로 주어지는 밭의 정보를 저장한 후 밭들간의 거리를 계산하여 간선을
형성해 비용 기준 최소힙에 저장한 후, 해당 힙을 이용하여 크루스칼 로직을 실행하며
MST를 구성하는 비용 합을 도출하면 쉽게 답을 구할 수 있었다.

유의할 점으론 비용이 C 미만인 간선(파이프)는 용납되지 않기 때문에
필자는 로직에서 간선을 형성하여 최소힙에 저장할 때 C 미만 비용의 간선들은
스킵하는 식으로 해당 조건을 구현하였다.

로직의 시간복잡도는 크루스칼의 $O(NlogN^2)$으로 수렴하고 이는 $N=2,000$인
최악의 경우에도 무난히 제한 조건 1초를 통과한다.
간선의 개수 = $N \times N-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.comparingInt(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());
        int N = parseInt(st.nextToken());
        int C = parseInt(st.nextToken());
        parent = new int[N];

        List<Point> points = new ArrayList<>();
        int x, y;
        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));
        }

        int w;
        for (int i = 0; i < points.size() - 1; i++)
            for (int j = i + 1; j < points.size(); j++) {
                w = getDist(points.get(i), points.get(j));

                if (w < C) continue;

                pq.offer(new Edge(i, j, w));
            }

        System.out.println(kruskal(N));
        br.close();
    }

    static int getDist(Point p1, Point p2) {
        int val1 = p2.x - p1.x;
        int val2 = p2.y - p1.y;

        return val1 * val1 + val2 * val2;
    }

    static long kruskal(int N) {
        Arrays.fill(parent, -1);
        int selected = 0;
        long 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, w;

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

}

결과