[백준 10021] Watering the Fields (Java)

 

www.acmicpc.net/problem/10021

10021번: Watering the Fields

풀이

N개의 필드 간 수로 파이프를 설치하는데, 모든 필드가 연결되도록 하는 최소 비용을 구하는 문제.

즉, 모든 필드를 잇는 최소 신장 트리(MST)를 도출해 내는 문제다.

 

그래프 내의 모든 정점을 잇는 트리를 신장 트리(Spanning Tree)라고 하며

그 중 사용된 간선 들의 가중치의 합이 최소가 되게 하는 신장 트리를 최소 신장 트리라고 한다.

gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

 

최소 신장 트리를 구현하는 방법 중 Kruskal MST 알고리즘을 이용하여 다음과 같은 방식으로 구현하였다.

 

1. 우선순위큐를 생성하여 모든 정점 사이의 유클리드 거리를 기준 오름차순으로 담든다.

- 우선순위큐에 거리 값을 직접 담는 것이 아니라 Node라는 객체를 담는다.

- Node는 시작 정점(start), 도착 정점(end), 두 정점 간 유클리드 거리(value)를 갖는다.

 

2. 정렬된 큐에서 Node를 하나씩 꺼내 최소 신장 트리에 적용이 될 수 있는 간선인지 체크한다.

- 꺼낸 Node의 value가 문제에서 주어진 조건인 C보다 작다면 넘어가도록 한다.

- 해당 간선이 여태껏 선택한 트리에 추가되었을 때, 사이클이 생기지 않는 지 체크한다.

 

사이클이 생기는 지 체크하기 위해서 유니온파인드 방식을 이용하였다.

유니온파인드 알고리즘 특성 상, 부모가 같다면 사이클이 발생하는 것으로 간주할 수 있다.

brenden.tistory.com/33

[알고리즘] 유니온 파인드 (Union-Find)

 

3. 적용이 될 수 있는 간선이라면 sum에 해당 Node의 value를 추가해주고, count++해준다.

- count 변수는 추가된 간선의 갯수를 나타낸다.

- 최소 신장 트리는 최소 N - 1개의 간선을 갖기 때문에 간선 갯수가 N-1이 된다면 탐색을 종료한다.

 

4. 최소 값을 출력한다.

- count가 N - 1이 아니라면 최소 신장 트리가 만들어지지 않는 케이스이다. 이 경우에는 -1을 출력한다.

- count가 N - 1이라면 최소 신장 트리가 만들어지는 케이스임을 의미하기 때문에 sum을 출력한다.

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    private static int N;
    private static int C;
    private static int[] x;
    private static int[] y;
    private static int[] parent;

    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());
        C = Integer.parseInt(st.nextToken());

        x = new int[N];
        y = new int[N];
        parent = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            x[i] = Integer.parseInt(st.nextToken());
            y[i] = Integer.parseInt(st.nextToken());
        }

        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> (int) (o1.value - o2.value));

        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                long dist = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);

                queue.offer(new Node(i, j, dist));
            }
        }

        int sum = 0;
        int count = 0;

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            if (node.value < C) {
                continue;
            }

            int x = node.start;
            int y = node.end;

            if (!isSameParent(x, y)) {
                sum += node.value;
                union(x, y);
                count++;
            }

            if (count == N - 1) {
                break;
            }
        }

        if (count != N - 1) {
            System.out.println(-1);

            return;
        }

        System.out.println(sum);
    }

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

        return find(parent[x]);
    }

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

        if (x != y) {
            parent[y] = x;
        }
    }

    private static boolean isSameParent(int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) {
            return true;
        }

        return false;
    }

    static class Node {
        private int start;
        private int end;
        private long value;

        public Node(int start, int end, long value) {
            this.start = start;
            this.end = end;
            this.value = value;
        }
    }
}