백준 - 행성 터널(2887) - 크루스칼 - Java

1. 문제

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

2. 풀이

두 행성 사이의 비용은 min(x좌표 차이, y좌표 차이, z좌표 차이)이다. 즉 3개중에 제일 적은 거리만 가지고 두 행성을 연결하면 되는 것이다. 따라서

1. x좌표, y좌표, z좌표끼리만 모아서 정렬하기.

2. 각 정렬된 값들에서 두 행성간의 차이(= 간선의 비용) 구하기.

   ex) 1번행성 x좌표 -1, 2번행성 x좌표 10이면 두 사이의 거리는 11이 될 것이고, 그러면 NodeList에 (11, 1번행성, 2번행성)을 넣어준다.
   이렇게 되면 x, y, z의 차이 중에서 가장 작은 것들이 NodeList앞에 오게 될 것이고, 차례로 꺼내서 크루스칼 알고리즘을 실행하면 된다.

3. 전체 코드

import java.util.*;

public class Main {
    
    static int parent[];
    
    public static void main(String args[]) {
        
        Scanner input = new Scanner(System.in);
        
        int N = input.nextInt();
        
        ArrayList<Position> Xlist = new ArrayList<Position>();
        ArrayList<Position> Ylist = new ArrayList<Position>();
        ArrayList<Position> Zlist = new ArrayList<Position>();
        
        parent = new int[N+1];
        
        for(int i = 1; i <= N; i++) {
            
            parent[i] = i;
            
            int x = input.nextInt();
            int y = input.nextInt();
            int z = input.nextInt();
            
            Xlist.add(new Position(x, i));
            Ylist.add(new Position(y, i));
            Zlist.add(new Position(z, i));
        }
        
        Collections.sort(Xlist);
        Collections.sort(Ylist);
        Collections.sort(Zlist);
        
        //정렬한다음에 하나씩 꺼내야겠지?
        ArrayList<Node> Nodelist = new ArrayList<Node>();
        
        for(int i = 0; i < N - 1; i++) {
            
            Nodelist.add(new Node(Xlist.get(i+1).distance - Xlist.get(i).distance,
                                 Xlist.get(i).node, Xlist.get(i+1).node));
            
            Nodelist.add(new Node(Ylist.get(i+1).distance - Ylist.get(i).distance,
                                 Ylist.get(i).node, Ylist.get(i+1).node));
            
            Nodelist.add(new Node(Zlist.get(i+1).distance - Zlist.get(i).distance,
                                 Zlist.get(i).node, Zlist.get(i+1).node));
        }
        
        Collections.sort(Nodelist);
        
        int answer = 0;
        
        for(int i = 0; i < Nodelist.size(); i++) {
            
            int a = Nodelist.get(i).A;
            int b = Nodelist.get(i).B;
            int cost = Nodelist.get(i).cost;
            
            if(find(a) != find(b)) {
                
                union(a, b);
                answer += cost;
            }
        }
        
        System.out.println(answer);
    }
    
    public static void union(int a, int b) {
        
        a = find(a);
        b = find(b);
        
        if(a < b)
            parent[b] = a;
        
        else
            parent[a] = b;
    }
    
    public static int find(int x) {
        
        if(parent[x] == x)
            return x;
        
        return parent[x] = find(parent[x]);
    }
    
    public static class Position implements Comparable<Position>{
        
        int distance;
        int node;
        
        public Position(int d, int node) {
            
            distance = d;
            this.node = node;
        }
        
        @Override
        public int compareTo(Position other) {
            
            if(this.distance == other.distance)
                return Integer.compare(this.node, other.node);
            
            return Integer.compare(this.distance, other.distance);
        }
    }
    
    public static class Node implements Comparable<Node> {
        
        int cost;
        int A;
        int B;
        
        public Node(int cost, int A, int B) {
            
            this.cost = cost;
            this.A = A;
            this.B = B;
        }
        
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.cost, other.cost);
        }
    }
}