[java 백준] 2887번 행성터널

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

2887번: 행성 터널

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main {
 
    public static class Point{
 
        int idx;
        int x;
        int y;
        int z;
 
      Point(int idx,int x,int y,int z){
            this.idx=idx;
            this.x=x;
            this.y=y;
            this.z=z;
        }
    }
 
    public static class Line implements Comparable<Line>{
 
        int to;
        int from;
        int weight;
 
        public Line(int to,int from,int weight){
            this.to=to;
            this.from=from;
            this.weight=weight;
        }
 
        @Override
 
        public int compareTo(Line other){
            return  this.weight-other.weight;
        }
    }
 
    public static int N;
    public static ArrayList<Line> lineList;
    public static int[] parents;
 
    public static int find(int x){
        if(x==parents[x]){
            return x;
        }
        return  parents[x]=find(parents[x]);
 
    }
 
    public static void union(int x,int y){
        x=find(x);
        y=find(y);
        if(x<y){
            parents[y]=x;
        }
        else{
            parents[x]=y;
        }
    }
 
 
 
    public static void main(String args[]) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N=Integer.parseInt(br.readLine());
 
        Point[] pointArr=new Point[N];//x,y,z 저장
        lineList=new ArrayList<>(); //간선에 대한 가중치 저장
        parents=new int[N];
        for(int i=0;i<N;i++){
 
            st=new StringTokenizer(br.readLine());
 
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());
            int c=Integer.parseInt(st.nextToken());
            pointArr[i]=new Point(i,a,b,c);
 
 
        }
 
 
 
        //x를 기준으로 정렬
        Arrays.sort(pointArr,(o1,o2)->o1.x-o2.x);
        for(int i=0;i<N-1;i++){
            int weight=Math.abs(pointArr[i].x-pointArr[i+1].x);
            lineList.add(new Line(pointArr[i].idx,pointArr[i+1].idx,weight));
 
        }
 
 
 
        //y를 기준으로 정렬
        Arrays.sort(pointArr,(o1,o2)->o1.y-o2.y);
        for(int i=0;i<N-1;i++){
            int weight=Math.abs(pointArr[i].y-pointArr[i+1].y);
            lineList.add(new Line(pointArr[i].idx,pointArr[i+1].idx,weight));
 
        }
 
 
        //z를 기준으로 정렬
        Arrays.sort(pointArr,(o1,o2)->o1.z-o2.z);
        for(int i=0;i<N-1;i++){
            int weight=Math.abs(pointArr[i].z-pointArr[i+1].z);
            lineList.add(new Line(pointArr[i].idx,pointArr[i+1].idx,weight));
 
        }
 
        Collections.sort(lineList);
 
        for(int i=0;i<N;i++){
            parents[i]=i;
        }
 
        int ans=0;
 
        for(int i=0;i<lineList.size();i++){
            Line line=lineList.get(i);
            int from=line.from;
            int to=line.to;
            if(find(from)!=find(to)){
                //사이클이 없어야 함 ! 빡구 ㄴㄴ
                ans+=line.weight;
                union(from,to);
            }
 
 
 
        }
        System.out.println(ans);
 
        //어차피 사이클 판별할거니까 어디서부터 시작하느냐는 중요하지 않음
        //cost가 최소여야 하니까 최소 간선을 뽑아내는게 더 중요!
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    }
 
}