행성 터널

 

문제

행성마다 x, y, z 좌표가 주어지고 총 n개의 행성이 있다.

행성마다의 거리는 Math.min(|x0-x1|, |y0-y1|, |z0-z1|}) 이다.

이 때, 최소한의 비용을 활용하여 모든 행성을 연결해야 한다.

 

 

로직

1. 데이터에 각각 인덱스를 리스트 말미에 삽입

2. 데이터 리스트에서 x를 기준으로 오름차순 정렬

3. 정렬된 데이터 중 앞에서부터 바로 자신의 뒤에 인덱스와 |x0-x1|을 구해 거리 리스트에 {차이 절대값, 현재 행성의 인덱스, 다음 행성의 인덱스} 삽입

-> 가능한 이유 : 우선적으로 x를 기준으로 정렬하면, x좌표로 정렬됨 따라서 x0과 x1을 비교하고 x0과 x2는 비교할 필요가 없어짐

-> 왜냐하면 거리가 무조건 적으로 x0-x1이 더 작기 때문에

• 또한 크루스칼 알고리즘에서 가장 중요한 것은 N개의 노드 중 N-1개의 간선만으로 충분히 최적의 연결방식을 찾을 수 있다.

4. y, z 도 위의 과정 진행

5. 이 후 크루스칼 알고리즘 실행

 

 

 

코드

public static void main(String[] args){
    int[][] data = {
        {11, -15, -15, 0},
        {14, -5, -15, 1},
        {-1, -1, -5, 2},
        {10, -4, -1, 3},
        {19, -4, 19, 4}
    };
    List<List<Integer>> check = new ArrayList<>();
    int[] parents = new int[5];
    for(int i=0; i<5; i++){
        parents[i] = i;
    }
    for(int i=0; i<3; i++){
        int now = i;
        Arrays.sort(data, Comparator.comparingInt(arr -> arr[now]));
        for(int j=0; j<data.length-1; j++){
            List<Integer> nowList = new ArrayList<>();
            nowList.add(Math.abs(data[j][now] - data[j+1][now]));
            nowList.add(j);
            nowList.add(j+1);
            check.add(nowList);
        }
    }

    int result = 0;
    Collections.sort(check, Comparator.comparingInt(arr -> arr.get(0)));
    for(List<Integer> nowCheck : check){;
        int parent1 = find_paretns(parents, nowCheck.get(1));
        int parent2 = find_paretns(parents, nowCheck.get(2));
        if(parent1 != parent2){
            parents[parent1] = (parent1 > parent2) ? parent2 : parent1;
            parents[parent2] = (parent1 > parent2) ? parent2 : parent1;
            result += nowCheck.get(0);
        }
    }
    System.out.println(result);

}
public static int find_paretns(int[] parents, int node){
    if(node != parents[node]){
        parents[node] = find_paretns(parents, parents[node]);
    }
    return parents[node];
}