이코테 - 행성 터널 with JAVA

 

 

문제

최대 100000개의 행성이 있고 각 행성의 3차원 좌표가 주어진다. 이때, 행성 간 연결 비용은 행성 간 x값의 차이에 대한절대값, y값의 차이에 대한절대값, z값의 차이에 대한절대값 중 가장 작은값으로 측정된다. 최소한의 연결 비용을 통해 모든 행성을 연결하라.

 

 

 

로직

기본적으로는 크루스칼 알고리즘을 사용해야함이 읽힌다. '최소한의 비용을 통해 모든 노드를 연결하는 문제' 이기 때문이다.

하지만, 문제는 행성간 도로 설치 비용을 구하는 것이다. 만약 100000개의 행성들간 설치 비용을 모두 구한다면 문제가 발생한다.

(n)(n-1)/2를 해보면 수가 너무 커짐을 알 수 있다.

 

따라서 행성간 도로 설치 비용을 구하는 방식을 설정해야 한다.

문제에서 나온 도로 설치 비용을 자세히 보면 간단한 방법을 유추할 수 있다.

 

1. 우선, x축, y축, z축 리스트를 따로 두어 입력을 받는다.

2. 각각 값을 정렬한다.

3. 이 후 순차적으로 앞뒤의 차만 구하여 최종 리스트에 넣는다.

 

예를 들어, [11, -15, -15], [14, -5, -15], [-1, -1, -5] 가 있다고 가정하자.

우선 데이터는 아래와 같이 x,y,z에 인덱스 정보를 추가해 삽입한다.

 

x : [[11, 0], [14, 1], [-1, 2]]

y : [[-15, 0], [-5, 1], [-1, 2]]

z : [[-15, 0], [-15, 1], [-5, 2]]

 

이 후, 각각을 정렬한다.

x : [[-1, 2], [11, 0], [14, 1]]

y : [[-15, 0], [-5, 1], [-1, 2]]

z : [[-15, 0], [-15, 1], [-5, 2]]

 

다음으로는 앞뒤로만 연산을 수행한다.

x : (11 - -1) = 12, (14 - 11) = 3

y : (-5 - -15) = 10, (-1 - -5) = 4

z : (-15 - -15) = 0, (-5 - -15) = 10

 

문제에서 주어진 조건은 '최소 금액으로 모든 행성 연결'이다.

이를 다시 생각해보면, 행성간 최소한 하나의 선이라도 있으면 된다는 것이다.

즉, 예를 들어, x축 값을 기준으로 정렬하면 행성번호 순으로 3-4-1-2-5이다. 이 행성들간 거리를 큐에 넣는다면,

적어도 3-4-1-2-5는 x축을 기준으로 최소한의 금액으로 연결되는 것이다.

따라서, 모든 행성간 거리를 추측할 필요가 없어지는 것이다.

 

"예를 들어, 행성5는 x축에서는 행성2, y축에서는 행성3, 행성4, z축에서는 행성4와 가장 최단 경로를 가질 수 있다. 

이러한 경우, y축에서와 z축에서 행성4를 만나는데, 문제에서 주어진것처럼 가장 작은 값만이 경로이다. 따라서 이러한 부분은 크루스칼 알고리즘 처리시 자동적으로 해당 선을 넘긴다"

 

 

마지막으로, 종합 비용 리스트에 값과 인덱스를 넣고 정렬하면 된다.

 

 

 

코드

package JAVA.TCT.GraphTheory;

import java.util.*;

public class Q4 {
    public static int[] parent;
    public static void main(String[] args){
        // 정보 입력
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        parent = new int[n+1];
        for(int i=1; i<=n; i++){
            parent[i] = i;
        }
        List<List<Integer>> x = new ArrayList<>();
        List<List<Integer>> y = new ArrayList<>();
        List<List<Integer>> z = new ArrayList<>();
        for(int i=0; i<n; i++){
            x.add(Arrays.asList(sc.nextInt(), i+1));
            y.add(Arrays.asList(sc.nextInt(), i+1));
            z.add(Arrays.asList(sc.nextInt(), i+1));
        }
        // 정렬
        Collections.sort(x, Comparator.comparing(arr -> arr.get(0)));
        Collections.sort(y, Comparator.comparing(arr -> arr.get(0)));
        Collections.sort(z, Comparator.comparing(arr -> arr.get(0)));
        // 간선 정보 추출
        List<List<Integer>> edges = new ArrayList<>();
        for(int i=0; i<n-1; i++){
            // 거리, 행성인덱스1, 행성인덱스2
            edges.add(Arrays.asList(x.get(i+1).get(0)-x.get(i).get(0),
                    x.get(i).get(1), x.get(i+1).get(1)));
            edges.add(Arrays.asList(y.get(i+1).get(0)-y.get(i).get(0),
                    y.get(i).get(1), y.get(i+1).get(1)));
            edges.add(Arrays.asList(z.get(i+1).get(0)-z.get(i).get(0),
                    z.get(i).get(1), z.get(i+1).get(1)));
        }
        // 종합 정보 정렬
        Collections.sort(edges, Comparator.comparing(arr -> arr.get(0)));
        // 크루스칼 로직
        int result = 0;
        for(List<Integer> edge : edges){
            int cost = edge.get(0);
            int star1 = edge.get(1);
            int star2 = edge.get(2);
            int parent1 = find_parent(star1);
            int parent2 = find_parent(star2);
            if(parent1 == parent2){
                continue;
            }
            result += cost;
            union_parent(star1, star2);
        }
        System.out.println(result);
    }
    public static int find_parent(int star){
        if(parent[star] != star){
            parent[star] = find_parent(parent[star]);
        }
        return parent[star];
    }
    public static void union_parent(int star1, int star2){
        int parent1 = find_parent(star1);
        int parent2 = find_parent(star2);
        parent[parent1] = (parent1 > parent2) ? parent2 : parent1;
        parent[parent2] = (parent1 > parent2) ? parent2 : parent1;
    }
}

 

 

하지만 해당 코드를 돌려보면 메모리 초과가 발생한다.

이유는 명확히 아직 밝히지 못했다. 

하지만, 행성과 간선정보를 클래스로 만들어 Comparable을 구현해 compareTo 메서드 재정의해 사용하여 정렬을 구현하면 메모리 초과가 발생하지 않는다. 이유는 밝히지 못했지만 이러한 경우 사용하면 좋을 듯 하다.

 

 

 

package JAVA.TCT.GraphTheory;

import java.util.*;

class Point implements Comparable<Point>{
    public int value;
    public int index;
    public Point(int value, int index){
        this.value = value;
        this.index = index;
    }
    @Override
    public int compareTo(Point other){
        if(this.value == other.value){
            return Integer.compare(this.index, other.index);
        }
        return Integer.compare(this.value, other.value);
    }
}

class Edge implements Comparable<Edge>{
    public int distance;
    public int index1;
    public int index2;
    public Edge(int distance, int index1, int index2){
        this.distance = distance;
        this.index1 = index1;
        this.index2 = index2;
    }
    @Override
    public int compareTo(Edge other){
        if(this.distance < other.distance){
            return -1;
        }
        return 1;
    }
}

public class Q4 {
    public static int[] parent;
    public static void main(String[] args){
        // 정보 입력
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        parent = new int[n+1];
        for(int i=1; i<=n; i++){
            parent[i] = i;
        }
        List<Point> x = new ArrayList<>();
        List<Point> y = new ArrayList<>();
        List<Point> z = new ArrayList<>();
        for(int i=0; i<n; i++){
            x.add(new Point(sc.nextInt(), i+1));
            y.add(new Point(sc.nextInt(), i+1));
            z.add(new Point(sc.nextInt(), i+1));
        }
        // 정렬
        Collections.sort(x);
        Collections.sort(y);
        Collections.sort(z);
        // 간선 정보 추출
        List<Edge> edges = new ArrayList<>();
        for(int i=0; i<n-1; i++){
            // 거리, 행성인덱스1, 행성인덱스2
            edges.add(new Edge(x.get(i+1).value-x.get(i).value,
                    x.get(i).index, x.get(i+1).index));
            edges.add(new Edge(y.get(i+1).value-y.get(i).value,
                    y.get(i).index, y.get(i+1).index));
            edges.add(new Edge(z.get(i+1).value-z.get(i).value,
                    z.get(i).index, z.get(i+1).index));
        }
        // 종합 정보 정렬
        Collections.sort(edges);
        // 크루스칼 로직
        int result = 0;
        for(Edge edge : edges){
            int cost = edge.distance;
            int star1 = edge.index1;
            int star2 = edge.index2;
            int parent1 = find_parent(star1);
            int parent2 = find_parent(star2);
            if(parent1 == parent2){
                continue;
            }
            result += cost;
            union_parent(star1, star2);
        }
        System.out.println(result);
    }
    public static int find_parent(int star){
        if(parent[star] != star){
            parent[star] = find_parent(parent[star]);
        }
        return parent[star];
    }
    public static void union_parent(int star1, int star2){
        int parent1 = find_parent(star1);
        int parent2 = find_parent(star2);
        parent[parent1] = (parent1 > parent2) ? parent2 : parent1;
        parent[parent2] = (parent1 > parent2) ? parent2 : parent1;
    }
}