[BOJ] 행성 터널(2887)

[백준(BOJ)] 2887_행성 터널 JAVA

문제 : BOJ_2887번 행성 터널

문제 설명

3개의 좌표 (x,y,z)로 된 N 개의 행성이 있습니다.

두 행성을 연결할 수 있는 비용은 행성의 각 좌표의 차 중 최솟값이라고 합니다.

이때 모든 행성을 터널로 연결할 때 최소 비용을 구하는 문제입니다.

---

Solution

크루스칼 알고리즘

모든 노드를 연결하는 최소 비용의 터널을 구해야 하기 때문에 크루스칼 알고리즘을 사용해야 합니다.

주어진 터널이 없기 때문에 터널들을 비교하면서 최솟값의 터널을 찾아야 합니다.

이때 행성의 개수는 최대 100,000이 주어지므로, 모든 행성을 서로 비교해 준다면 시간 초과가 발생합니다.

잘 생각해 보면 행성 간의 최솟값은 항상 x, y, z 값의 차의 최솟값 중 하나이기 때문에, x 값의 차가 최소인 행성 터널, y 값의 차가 최소인 행성 터널, z 값의 차가 최소인 행성 터널들을 만들어서 비교해 준다면, 3*N 개의 터널로 크루스칼 알고리즘을 수행해 문제를 해결할 수 있습니다.

---

Description

• 크루스칼 알고리즘의 시간 복잡도는 E*log(E)입니다.
• 각 좌표의 인덱스와 좌표값을 저장해 주는 Pair, 한 행성의 좌표를 비교해 주는 Node 클래스를 만들었습니다.
• 크루스칼 알고리즘 사용을 위해 union-find 알고리즘을 구현했습니다.

---

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

class Node{
    private int x;
    private int y;
    private int z;

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getZ() {
        return z;
    }

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

class Pair implements Comparable<Pair>{
    private int idx;
    private int value;
    public Pair(int idx, int value){
        this.idx = idx;
        this.value = value;
    }

    public int getIdx() {
        return idx;
    }

    public int getValue() {
        return value;
    }

    @Override
    public int compareTo(Pair other) {
        return Integer.compare(this.value,other.value);
    }
}

class ConnectSpace implements Comparable<ConnectSpace>{
    private int go;
    private int ed;
    private int value;

    public ConnectSpace(int go, int ed, int value){
        this.go = go;
        this.ed = ed;
        this.value = value;
    }

    public int getGo() {
        return go;
    }

    public int getEd() {
        return ed;
    }

    public int getValue() {
        return value;
    }

    @Override
    public int compareTo(ConnectSpace other) {
        return Integer.compare(this.value,other.value);
    }
}

public class Main {

    public static ArrayList<Node> nodeArr = new ArrayList<>();
    public static ArrayList<Pair> xArr = new ArrayList<>();
    public static ArrayList<Pair> yArr = new ArrayList<>();
    public static ArrayList<Pair> zArr = new ArrayList<>();
    public static ArrayList<ConnectSpace> searchArr = new ArrayList<>();
    public static int calcDist(Node a, Node b){
        return Math.min(Math.abs(a.getX()-b.getX()) , Math.min(Math.abs(a.getY()-b.getY()) , Math.abs(a.getZ() - b.getZ())));
    }

    public static int n;
    public static int[] parent;
    public static int sum;
    public static int find(int idx){
        if(idx==parent[idx]) return idx;
        else return parent[idx] = find(parent[idx]);
    }
    public static void merge(int x ,int y){
        x = find(x);
        y = find(y);
        if(x==y) return;
        if(x<y) parent[y] = x;
        else parent[x] = y;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        parent = new int[n];
        for(int i=0; i<n; i++) parent[i] = i;
        for(int i=0;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());
            nodeArr.add(new Node(x,y,z));
            xArr.add(new Pair(i,x));
            yArr.add(new Pair(i,y));
            zArr.add(new Pair(i,z));
        }

        Collections.sort(xArr);
        Collections.sort(yArr);
        Collections.sort(zArr);

        for(int i=0; i<n-1; i++){
            searchArr.add(new ConnectSpace(xArr.get(i).getIdx(), xArr.get(i+1).getIdx() , calcDist(nodeArr.get(xArr.get(i).getIdx()),nodeArr.get(xArr.get(i+1).getIdx()))));
            searchArr.add(new ConnectSpace(yArr.get(i).getIdx(), yArr.get(i+1).getIdx() , calcDist(nodeArr.get(yArr.get(i).getIdx()),nodeArr.get(yArr.get(i+1).getIdx()))));
            searchArr.add(new ConnectSpace(zArr.get(i).getIdx(), zArr.get(i+1).getIdx() , calcDist(nodeArr.get(zArr.get(i).getIdx()),nodeArr.get(zArr.get(i+1).getIdx()))));
        }

        Collections.sort(searchArr);

        for(int i=0; i<searchArr.size();i++){
            int go = searchArr.get(i).getGo();
            int ed = searchArr.get(i).getEd();
            int value = searchArr.get(i).getValue();

            if(find(go)==find(ed)) continue;
            else {
                merge(go,ed);
                sum += value;
            }
        }
        bw.write(String.valueOf(sum)+"\n");
        bw.flush();
        br.close();
        bw.close();
    }
}