BOJ 10021 - Watering the Fields

10021번: Watering the Fields

 

N개의 필드 존재 (1 ≤ N ≤ 2000)

각 필드는 2차원 평면상 (xi, yi)로 표시(0≤ xi, yi ≤ 1000)

$$ i,j 필드 사이 비용 = (x_i-x_j)^2 + (y_i-y_j)^2 $$

모든 필드를 최소비용으로 연결하고 싶다.

그런데 비용이 C 이상인 파이프만 설치할 수 있다. (1≤ C≤ 1,000,000)

크루스칼 알고리즘을 사용하면 될 것 같다.

1. 주어진 정보로 간선을 계산해 저장한다.
2. 비용이 작은 간선부터 꺼내 두 노드를 연결한다.
3. 노드 연결 시 이미 같은 집합이거나 비용이 C보다 작다면 연결하지 않는다.

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ10021 {

    static class Edge {
        int from;
        int to;
        int cost;

        public Edge(int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }

        @Override
        public String toString() {
            return from + "," + to + "," + cost;
        }
    }

    static FastReader scan = new FastReader();
    static int N, C;
    static int[][] fields;
    static List<Edge>[] graph;

    static void input() {
        N = scan.nextInt();
        C = scan.nextInt();
        fields = new int[N][2];
        for (int i = 0; i < N; i++) {
            fields[i] = new int[]{scan.nextInt(), scan.nextInt()};
        }
    }

    static void initGraph() {
        graph = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<>();
        }

        // 각 노드부터 출발한 거리 계산
        for (int i = 0; i < N; i++) {
            int[] from = fields[i];
            for (int j = i + 1; j < N; j++) {
                int[] to = fields[j];
                int cost = calcCost(from, to);
                graph[i].add(new Edge(i, j, cost));
            }
        }
    }

    static int calcCost(int[] from, int[] to) {
        return (int) (Math.pow((from[0] - to[0]), 2) + Math.pow((from[1] - to[1]), 2));
    }

    static void solve() {
        int totalCost = 0;
        int edgeCount = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.cost));
        for (int i = 0; i < N; i++) {
            for (Edge e : graph[i]) {
                if (e.cost < C) continue;
                pq.add(e);
            }
        }
        int[] parent = new int[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
        }
        while (!pq.isEmpty()) {
            Edge curr = pq.poll();
            int from = curr.from;
            int to = curr.to;
            int cost = curr.cost;

            if (isConnected(parent, from, to)) {
                continue;
            }

            union(parent, from, to);
            totalCost += cost;
            edgeCount++;
        }

        System.out.println(edgeCount == N - 1 ? totalCost : -1);
    }

    static boolean isConnected(int[] parent, int x, int y) {
        return find(parent, x) == find(parent, y);
    }

    static void union(int[] parent, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);

        if (rootX < rootY) {
            parent[rootY] = rootX;
        } else {
            parent[rootX] = rootY;
        }
    }

    static int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }

    public static void main(String[] args) {
        input();
        initGraph();
        solve();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}