[백준] 2887번 : 행성 터널

2887번: 행성 터널

# 문제

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

# 입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

# 출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

# 예제 입력 1

5

11 -15 -15

14 -5 -15

-1 -1 -5

10 -4 -1

19 -4 19

# 예제 출력 1

4

---

3차원 공간에 행성들이 N개 존재할 때 최소 비용으로 각 행성들을 모두 연결하는 문제이다. 행성A(x1, y1, z1)과 행성B(x2, y2, z2)를 연결하는 비용은 min( abs(x1-x2), abs(y1-y2), abs(z1-z2) )라고 한다. 먼저 시간초과가 나온 방법을 적고 그 다음 통과한 방법을 소개하고자 한다.

 

처음에 vertex[v+1][3]라는 배열에 입력값을 받아 각 행성의 (x, y, z)를 입력받았다. 그리고 V(정점의 개수)번 만큼 Loop를 돌리고, 그 안에 다시 V/2번의 Loop를 돌려 i번 행성을 기준으로 j번 행성과 비교하며 가중치가 최저인 곳을 찾는다. 최저인 곳을 찾아서 i번 행성과 j번 행성이 연결되어있지 않으면 연결하는 방법으로 했다.

 

        int sum = 0;
        
        for(int i=1; i<=v; i++){
        
            int min = 999999999;
            int index = 0;
            
            for(int j=i+1; j<=v; j++){

                int tmp = min(
                	Math.abs(vertex[i][0] - vertex[j][0]),
                	Math.abs(vertex[i][1] - vertex[j][1]), 
                	Math.abs(vertex[i][2] - vertex[j][2]));
                
                if (tmp < min) {
                    index = j;
                    min = tmp;
                }
            }
            
            if(index == 0) continue;
            if(!findParent(parent, i, index)){ //i번 행성과 index번 행성이 연결되어 있지 않으면
                sum += min; //합을 더하고
                unionParent(parent, i, index); //서로 연결한다
            }
        }

이 방법을 쓰면 코드도 간결하고 간선에 대한 정보도 필요없으며 정렬을 하지 않을 수 있지만, V * V / 2번의 루프를 돌고 그 안에서 루프 1번 당 5번의 비교가 일어나며 Union-Find에 대한 재귀 또한 발생하여 메모리와 시간이 상당히 많이 소요된다. 행성의 개수가 1<= V <= 100,000 이므로 행성이 10만개라면 50억 번의 loop를 돌게된다. 따라서 시간 초과 혹은 메모리 초과가 발생할 것 이다.

---

그럼 정렬도 해야하고 간선에 대한 정보도 생성해서 MST를 만드는 방법을 보자.

입력으로 주어지는 각 행성의 x, y, z를 받는 배열은 동일하다. 다만 vertex[v+1][3] --> vertex[v+1][4]로 변경하여 4번째 원소에 행성의 번호를 입력하자. vertex[i] = { x좌표, y좌표, z좌표, i}가 될 것이다. 이 후

 

X 좌표에 대해 정렬 + 간선 정보 생성

Y 좌표에 대해 정렬 + 간선 정보 생성

Z 좌표에 대해 정렬 + 간선 정보 생성

 

즉 모든 정점끼리 서로 간선을 만드는데 X 기준 오름차순일 때의 간선 집합, Y 기준 오름차순일 때의 간선 집합, Z 기준 오름차순일 때의 간선 집합. 총 3개의 간선 집합으로 구성될 것이다.

 

이렇게 만들어진 간선은 총 3 * (V - 1)개가 될 것이다. 간선들을 '가중치'를 기준으로 한번 더 정렬한다.

 

이렇게 하면 크루스칼 알고리즘으로 최소 신장 트리를 만드는 조건이 모두 충족되었으므로 MST만 만들어주면 된다.

    //정렬을 위한 Comparator 인터페이스를 구현, 생성자를 통해 xyz 멤버를 주입해
    //x, y, z중 하나를 정렬
    static class IntComparator implements Comparator<int[]> {

        int xyz;
        public IntComparator(int xyz){
            this.xyz = xyz;
        }

        @Override
        public int compare(int[] o1, int[] o2) {
            if(o1[xyz] > o2[xyz]) return 1;
            else if(o1[xyz] < o2[xyz]) return -1;
            return -1;
        }
    }
    //간선의 정보를 갖는 Edge 클래스
    static class Edge{
        int[] v = new int[2];
        int w;

        public Edge(int v1, int v2, int w){
            this.v[0] = v1;
            this.v[1] = v2;
            this.w = w;
        }
    }

        int idx = 0;

        IntComparator x_comp = new IntComparator(0); //x기준 정렬
        Arrays.sort(vertex, 1, v+1, x_comp);
        for(int i=1; i<v; i++) 
        	edges[idx++] = new Edge(vertex[i][3], vertex[i+1][3], vertex[i+1][0] - vertex[i][0]);

        IntComparator y_comp = new IntComparator(1); //y기준 정렬
        Arrays.sort(vertex, 1, v+1, y_comp);
        for(int i=1; i<v; i++) 
        	edges[idx++] = new Edge(vertex[i][3], vertex[i+1][3], vertex[i+1][1] - vertex[i][1]);

        IntComparator z_comp = new IntComparator(2); //z기준 정렬
        Arrays.sort(vertex, 1, v+1, z_comp);
        for(int i=1; i<v; i++) 
        	edges[idx++] = new Edge(vertex[i][3], vertex[i+1][3], vertex[i+1][2] - vertex[i][2]);

        List<Edge> list = Arrays.asList(edges.clone());

		//가중치를 기준으로 간선들 정렬
        EdgeComparator edgeComparator = new EdgeComparator();
        list.sort(edgeComparator);

        //크루스칼 알고리즘
        int sum = 0;
        
        for(int i=0; i<3*(v-1); i++){

            Edge edge = list.get(i);

            if(!findParent(parent, edge.v[0], edge.v[1])){
                sum += edge.w;
                unionParent(parent, edge.v[0], edge.v[1]);
            }
        }

이 방법을 쓰면 (정렬 + V-1번의 loop) * 3 + ((V-1) * 3번의 루프 + Union-Find) 의 시간 복잡도를 쓰므로 처음의 방법보다 훨씬 적은 리소스가 소모된다.

 

# Code </>

public class Main {

    static class EdgeComparator implements Comparator<Edge>{
        @Override
        public int compare(Edge e1, Edge e2) {
            int w1 = e1.w;
            int w2 = e2.w;

            if(w1 < w2) return -1;
            else if(w1 > w2) return 1;
            else return 0;
        }
    }

    static class IntComparator implements Comparator<int[]> {

        int xyz;
        public IntComparator(int xyz){
            this.xyz = xyz;
        }

        @Override
        public int compare(int[] o1, int[] o2) {
            if(o1[xyz] > o2[xyz]) return 1;
            else if(o1[xyz] < o2[xyz]) return -1;
            return -1;
        }
    }
    static class Edge{
        int[] v = new int[2];
        int w;

        public Edge(int v1, int v2, int w){
            this.v[0] = v1;
            this.v[1] = v2;
            this.w = w;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "v=" + Arrays.toString(v) +
                    ", w=" + w +
                    '}';
        }
    }
    static int getParent(int[] parent, int x){
        if(parent[x] == x) return x;
        return getParent(parent, parent[x]);
    }
    static void unionParent(int[] parent, int a, int b){
        a = getParent(parent, a);
        b = getParent(parent, b);

        if(a < b) parent[b] = a;
        else parent[a] = b;
    }
    static boolean findParent(int[] parent, int a, int b){
        a = getParent(parent, a);
        b = getParent(parent, b);
        return a == b?true:false;
    }

    static int min(int a, int b, int c){
        int min = Math.min(a, b);
        return min < c?min:c;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int v = Integer.parseInt(br.readLine());

        Edge[] edges = new Edge[3*(v-1)];
        int[][] vertex = new int[v+1][4];
        int[] parent = new int[v+1];

        for(int i=1; i<=v; i++)
            parent[i] = i;

        for(int i=1; i<=v; i++){
            st = new StringTokenizer(br.readLine());

            vertex[i][0] = Integer.parseInt(st.nextToken());
            vertex[i][1] = Integer.parseInt(st.nextToken());
            vertex[i][2] = Integer.parseInt(st.nextToken());
            vertex[i][3] = i;
        }

        int idx = 0;

        IntComparator x_comp = new IntComparator(0); //x
        Arrays.sort(vertex, 1, v+1, x_comp);
        for(int i=1; i<v; i++) edges[idx++] = new Edge(vertex[i][3], vertex[i+1][3], vertex[i+1][0] - vertex[i][0]);

        IntComparator y_comp = new IntComparator(1); //y
        Arrays.sort(vertex, 1, v+1, y_comp);
        for(int i=1; i<v; i++) edges[idx++] = new Edge(vertex[i][3], vertex[i+1][3], vertex[i+1][1] - vertex[i][1]);

        IntComparator z_comp = new IntComparator(2); //z
        Arrays.sort(vertex, 1, v+1, z_comp);
        for(int i=1; i<v; i++) edges[idx++] = new Edge(vertex[i][3], vertex[i+1][3], vertex[i+1][2] - vertex[i][2]);

        List<Edge> list = Arrays.asList(edges.clone());

        EdgeComparator edgeComparator = new EdgeComparator();
        list.sort(edgeComparator);

        int sum = 0;
        for(int i=0; i<3*(v-1); i++){

            Edge edge = list.get(i);

            if(!findParent(parent, edge.v[0], edge.v[1])){
                sum += edge.w;
                unionParent(parent, edge.v[0], edge.v[1]);
            }
        }
        System.out.println(sum);
    }
}