백준 2887 (행성 터널) - java

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

2887번: 행성 터널

문제 :

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)

 

유형 : MST  

접근

• N-1 개의 간선을 선택하여 모든 행성이 연결 (최소 비용) 이라는 조건을 보면 MST를 만들라는 문제이다. MST는 크게 크루스칼과 프림 알고리즘을 사용하여 해결할 수 있는데 나는 크루스칼 알고리즘을 사용했다.
• 주의해야 할점은 간선이다. 입력의 수가 10만개이므로 모든 간선을 고려할 경우 메모리 초과가 발생한다.

간선 기준

• 문제를 보면 간선에 대한 조건이 나온다. min(|xA-xB|, |yA-yB|, |zA-zB|)
  • 해당 조건을 보고 초기 간선의 개수를 줄여야 한다. 답은 간단하면서도 생각하기 어려웠다. x,y,z 좌표를 기준으로 오름차순 정렬을 하여 (i,i+1) 번째의 차를 간선으로 잡으면 되는 것이다. -> 총 3(n-1)개의 간선
• 왜 ?
  • 오름차순을 정렬할 경우 우리가 알 수 있는 것은 (i-1,i+1)보다 (i,i+1)이 무조건 짧다는 것이다 !!!!! (같을 수는 있다)

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;

    static int[] root;

    static ArrayList<Integer>[] graph;
    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());
        Node[] node = new Node[n+1];
        root = new int[n+1];

        Point[] arrX = new Point[n];
        Point[] arrY = new Point[n];
        Point[] arrZ = new Point[n];

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());

            arrX[i-1] = new Point(i,x);
            arrY[i-1] = new Point(i,y);
            arrZ[i-1] = new Point(i,z);

            node[i] = new Node(x,y,z);
            root[i] = i;
        }

        Arrays.sort(arrX,(x,y) -> x.v - y.v);
        Arrays.sort(arrY,(x,y) -> x.v - y.v);
        Arrays.sort(arrZ,(x,y) -> x.v - y.v);

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

        for(int i=0;i<n-1;i++){
            pq.add(new Node(arrX[i].idx,arrX[i+1].idx,dis(arrX[i].v , arrX[i+1].v)));
            pq.add(new Node(arrY[i].idx,arrY[i+1].idx,dis(arrY[i].v , arrY[i+1].v)));
            pq.add(new Node(arrZ[i].idx,arrZ[i+1].idx,dis(arrZ[i].v , arrZ[i+1].v)));
        }

        get(pq);
        br.close();
    }

    static void get(PriorityQueue<Node> pq){

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

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

            if(num == n-1)
            {
                break;
            }
        }

        System.out.println(result);
    }

    static int dis(int a,int b){
       return Math.abs(a - b);
    }

    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;
        }
    }

}
class Point{
    int idx;
    int v;

    Point(int idx,int v){
        this.idx = idx;
        this.v = v;
    }
}
class Node{
    int x;
    int y;
    int z;

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