[백준] Q2887 행성 터널 JAVA

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

2887번: 행성 터널

1. 문제의 유형 및 이해

그래프 탐색, 최소 스패닝 트리, 정렬

행성을 효율적으로 지배하기 위해 각 행성을 연결하는 터널을 만들려고 할 때, 

터널 N-1개를 건설하여 모든 행성이 서로 연결되도록 하는 터널의 최소 비용을 구해보자.

행성 A(a,b,c)와 행성 B(x,y,z)의 터널의 비용은 min(|a-x|,|b-y|,|c-z|)로 정해진다.

 

주어지는 N개의 노드를 최소 비용으로 연결하는 최소 스패닝 트리 문제이다.

주어진 문제에서의 문제점은 N의 개수가 100,000개로 모두 연결하는 간선을 구한다면,

$_{100000}C_{2}$로 매우 크다는 점이다.

2. 문제 접근 방법

최소 스패닝 트리를 구하는 여러 알고리즘 중 대표적인 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있다.

우선순위 큐를 사용하는 경우

크루스칼 알고리즘은 O(ElogE) 프림 알고리즘은 O(ElogV + VlogV)로 

간선의 수가 적은 경우 크루스칼 알고리즘이 유리하고, 간선의 수가 많다면 프림 알고리즘이 유리하다.

 

단순하게 생각하면 간선의 수가 많은 프림 알고리즘이 유용하다고 생각할 수 있지만, 애초에 모든 간선을 구하는데에만 시간이 많이 걸린다.

 

그럼 여기서 생각해보아야할 문제가 모든 간선을 보아야 할까? 라는 의문이 들게 된다.

기준선에 대한 모든 행성의 정사영을 생각해보면 점선으로 이루어진 행성들이 존재하고 이들로만 모두를 연결할 수 있다. 

또한 최소 스패닝 트리를 이루기 위해 선택된 노드에서 연결할 수 있는 최소의 거리를 택하게 되는데, 각 축으로 행성을 내렸을 때 가장 가까이 있는 행성들로 노드마다 총 6개 이하 최소 간선들을 만들어 낼 수 있다.

 

그렇다면 다시 의문, 만들어진 스패닝 트리에서 한 노드에 7개 이상의 노드가 연결되는 경우가 있을 수도 있는 것 아닌가요?

 

어떠한 기준 노드로 부터 각각의 축 x, y, z으로 내렸을 때, 가장 가까운 점들이라고 가정하자.

기준 노드에 새로운 어떠한 점 '빨간 점'이 들어와서 총 7개의 간선이 연결되어 있다고 생각했을 때, 

이 노드는 각각의 축에 내렸을 때  두 가지 경우가 생긴다.

1. 각 노드 사이에 내려가는 경우

 > 이 경우 가정이 틀려진다.

2. 모든 노드 바깥에 떨어지는 경우

 > 이 경우 가장 가까운 새로운 노드의 6가지 간선 중 하나에 연결되어 있다.

그래서 우리는 각 노드에 대해 각 축에 내렸을 때 가장 가까운 노드들에 대해서만 간선을 구해주어도 스패닝 트리를 구성할 수 있다.

 

한쪽을 기준으로 보았을 때 총 3V개의 간선이 생기게 되고 밀집그래프의 기준에 미치지 못하므로 크루스칼 알고리즘을 통해 최소 스패닝 트리를 구성하도록 한다.

 

package solvedac.level5.gold1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


/**
 * @author : pcrmcw0486
 * @문제번호 : Q2887
 * @문제이름 :
 * @난이도 :
 * @date : 2022-02-28 오후 9:26
 * @문제이해 왕국은 N개의 행성으로 이루어진다.
 * A(x,y,z)와 B(a,b,c) 의 연결 최소 비용은 mi(|x-a| , |y-b| , |z-c|)
 * N-1개의 행성을 연결해보자.
 * @알고리즘 Minimum spannig tree
 * kruskal
 * @접근방법
 *  * N 100,000 >> NC2 = 100000*100001/2 = 50억
 *  모든 edge들을 보기에는 너무 많다.
 *  굳이 다 보아야할까?
 *  보아야할것만 생각해보자.
 *  각 행성마다 갈 수 있는 최소 간선만 고려해본다면, x로 갈 수 있는 최소, y,z 총 3가지의 행성이 '선택'되게 된다.
 *  행성이 다른 모든 행성들에 대해 다 고려해야하는가?
 *  우리가 spanning tree를 구성하면서 선택하는 간선들에 대해 생각해보자.
 *  kruskal알고리즘을 통해서 '그리디'하게 최소 거리의 간선을 택하게 된다. 굳이 멀리 있는 간선까지 포함하여 생각할 필요가 없다.
 *  즉, 총 3개의 그래프에서
 */

public class Main {
    static class Edge implements Comparable<Edge>{
        int x,y, dist;

        public Edge(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }

        @Override
        public int compareTo(Edge o) {
            return this.dist - o.dist;
        }
    }
    static class Point implements Comparable<Point>{
        int idx, value;

        public Point(int idx, int value) {
            this.idx = idx;
            this.value = value;
        }

        public int compareTo(Point o) {
            return this.value - o.value;
        }
    }
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;
        int N = Integer.parseInt(br.readLine());
        ArrayList<Point> listX = new ArrayList<>();
        ArrayList<Point> listY = new ArrayList<>();
        ArrayList<Point> listZ = new ArrayList<>();
        parent = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            listX.add(new Point(i, Integer.parseInt(st.nextToken())));
            listY.add(new Point(i, Integer.parseInt(st.nextToken())));
            listZ.add(new Point(i, Integer.parseInt(st.nextToken())));
            parent[i] = i;
        }
        Collections.sort(listX);
        Collections.sort(listY);
        Collections.sort(listZ);
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        for (int i = 0; i < N - 1; i++) {
            Point x,y;
            x = listX.get(i); y = listX.get(i + 1);
            pq.add(new Edge(x.idx, y.idx, Math.abs(x.value - y.value)));
            x = listY.get(i); y = listY.get(i + 1);
            pq.add(new Edge(x.idx, y.idx, Math.abs(x.value - y.value)));
            x = listZ.get(i); y = listZ.get(i + 1);
            pq.add(new Edge(x.idx, y.idx, Math.abs(x.value - y.value)));
        }

        int cnt= 0;
        long ans =0;
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            if (union(cur.x, cur.y)) {
                ans += cur.dist;
                cnt++;
            }
            if(cnt == N-1) break;
        }
        System.out.println(ans);
    }

    public static int find(int x) {
        if(parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    public static boolean union(int x, int y) {
        x = find(x);
        y = find(y);
        if( x==y) return false;
        parent[x] = y;
        return true;
    }
}