백준 10021 (Watering the Fields) - java

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

10021번: Watering the Fields

문제

비가 부족하여 농부 John은 N개의 밭(1 <= N <= 2000) 사이에 물을 보내기 위한 관개 시스템을 구축하려고 합니다.

각 필드 i는 2D 평면에서 고유한 점(xi, yi)으로 설명되며 0 <= xi, yi <= 1000입니다. 두 필드 i와 j 사이에 수도관을 건설하는 비용은 유클리드 거리의 제곱과 같습니다. 그들 사이에:

(xi - xj)^2 + (yi - yj)^2

FJ는 모든 밭이 서로 연결되어 모든 밭의 물이 일련의 파이프를 따라 다른 밭에 도달할 수 있도록 최소 비용의 파이프 시스템을 구축하고 싶습니다.

불행하게도 FJ의 관개 시스템 설치를 돕고 있는 계약자는 비용(유클리드 길이의 제곱)이 최소 C(1 <= C <= 1,000,000)가 아니면 파이프 설치를 거부합니다.

FJ가 그의 모든 분야를 파이프 네트워크와 연결하기 위해 지불해야 하는 최소 금액을 계산하도록 도와주세요.

• 요약하자면 두 지점 사이의 거리 계산은 (xi - xj)^2 + (yi - yj)^2로 한다.
• 모든 지점에서 다른 지점으로 이동 가능해야한다.
• 거리의 합이 최소 금액이면서 각 거리가 k값 이상이어야 한다.

유형 : MST

 

고찰

• MST가 완성되었는지 조건은 무엇일까 ? -> n-1개의 간선이 선택되었는가 이다
• MST를 만드는 방법은 -> 크루스칼 , 프림 알고리즘

전체 코드

import java.util.*;
import java.io.*;

public class Main {

    static int n = 0;
    static int m = 0;

    static int[] root;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        Point[] board = new Point[n+1];
        root = new int[n+1];

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            board[i] = new Point(x,y);
            root[i] = i;
        }

        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> x.c - y.c
        );

        for(int i=1;i<n;i++){
            for(int j=2;j<=n;j++){
                int tmp = dis(board[i],board[j]);

                if(tmp >= m){
                    pq.add(new Node(i,j,tmp));
                }
            }
        }

        int result = 0;
        int num = 0;
        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(num == n-1)
                break;

            if(find(cur.x) != find(cur.y)){
                union(cur.x,cur.y);
                result += cur.c;
                num = num + 1;
            }
        }

        if(num != n-1)
            System.out.println(-1);
        else
            System.out.println(result);
        br.close();
    }

    static int find(int x){
        if(root[x] == x)
            return root[x];

        return root[x] = find(root[x]);
    }

    static void union(int x,int y){
        x = find(x);
        y = find(y);

        if(x < y)
            root[y] = x;

        else
            root[x] = y;
    }


    static int dis(Point x,Point y){
        int nx = (x.x - y.x);
        int ny = (x.y - y.y);

        return (nx*nx + ny*ny);
    }
}
class Point{
    int x;
    int y;

    Point(int x,int y){
        this.x = x;
        this.y = y;
    }
}

class Node{
    int x;
    int y;
    int c;

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