[백준] 2887번 행성 터널 (platinum 5

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

class Point{
    int n;
    int v;
    public Point(int n,int v){
        this.n=n;
        this.v=v;
    }
}

class Node{
    int n1;
    int n2;
    int v;
    public Node(int n1, int n2, int v){
        this.n1=n1;
        this.n2=n2;
        this.v=v;
    }
}
public class Main{
    static int[] num;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int t=Integer.valueOf(br.readLine());

        //x,y,z별로 정렬 이유는 x,y,z의 값의 차이에 따라 mst에 추가해야함.
        //정렬을 해서  차이가 적게 나는 경우부터 추가하는게 편함
        PriorityQueue<Point> qx=new PriorityQueue<>(new Comparator<Point>(){
            public int compare(Point o1, Point o2){
                return o1.v-o2.v;
            }
        });
        PriorityQueue<Point> qy=new PriorityQueue<>(new Comparator<Point>(){
            public int compare(Point o1, Point o2){
                return o1.v-o2.v;
            }
        });
        PriorityQueue<Point> qz=new PriorityQueue<>(new Comparator<Point>(){
            public int compare(Point o1, Point o2){
                return o1.v-o2.v;
            }
        });
        PriorityQueue<Node> que=new PriorityQueue<>(new Comparator<Node>(){
            public int compare(Node o1, Node o2){
                return o1.v-o2.v;
            }
        });

        StringTokenizer st;
        for(int i=1; i<=t; i++){
            st=new StringTokenizer(br.readLine());
            int x=Integer.valueOf(st.nextToken());
            int y=Integer.valueOf(st.nextToken());
            int z=Integer.valueOf(st.nextToken());

            qx.offer(new Point(i,x));
            qy.offer(new Point(i,y));
            qz.offer(new Point(i,z));
        }

        int tv=0;
        int tn=0;

        //정점끼리의 차를 que에 추가하기. 즉 간선추가.
        Point p=qx.poll();
        tv=p.v;
        tn=p.n;
        while(!qx.isEmpty()){
            p=qx.poll();
            que.offer(new Node(tn, p.n, Math.abs(tv-p.v)));
            tv=p.v;
            tn=p.n;
        }

        p=qy.poll();
        tv=p.v;
        tn=p.n;
        while(!qy.isEmpty()){
            p=qy.poll();
            que.offer(new Node(tn, p.n, Math.abs(tv-p.v)));
            tv=p.v;
            tn=p.n;
        }

        p=qz.poll();
        tv=p.v;
        tn=p.n;
        while(!qz.isEmpty()){
            p=qz.poll();
            que.offer(new Node(tn, p.n, Math.abs(tv-p.v)));
            tv=p.v;
            tn=p.n;
        }

        long answer=0;
        int planet=0;
        num=new int[t+1];
        for(int i=1; i<=t; i++){
            num[i]=i;
        }

        if(que.size()==0){
            System.out.println(0);
        }
        else{
            //유니온 파인드로 정점들간에 중복. 혹은 겹치는 경우를 제외하고 추가한다.
            while(!que.isEmpty()){
                Node temp=que.poll();
                if(Find(temp.n1) == Find(temp.n2)){
                    continue;
                }
                Union(temp.n1,temp.n2);
                answer+=temp.v;
                planet++;
                if(planet==t-1){
                    break;
                }
            }
            bw.write(answer+"");
            bw.flush();
        }
    }
    public static int Find(int a){
        if(a==num[a]){
            return a;
        }
        else return num[a]=Find(num[a]);
    }

    public static void Union(int a, int b){
        int fa=Find(a);
        int fb=Find(b);
        if(fa!=fb){
            num[fa]=fb;
        }
    }

}

//이 문제는 다 생각해내고 마지막에서 헤매게 되었다.
//이유는 정점들 간의 경로에서 문제가 생겼는데, mst를 prim으로만 해결하다보니 union-find구현,
//정확한 적용을 모르고 있었다. prim으로 해결할 수 있을 것 같지만 출발점에서 다른 점으로 가다가, 다른 점에서
//출발점으로 들어올 때, 또 이런 경우가 여러번 발생가능. 이를 분류하는게 prim으로는 너무 복잡했고,
//결국 union-find개념을 익히고 해결하니 간단하게 해결되었다.