[백준] 2887번 행성 터널

문제 설명

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

문제 풀이

• 최소 신장 트리를 사용하여 풀이하였다.
• 우선 최소 신장 트리 알고리즘을 프림(N^2), 크루스칼(ElogE) 두가지가 존재한다.
• 간선의 갯수를 고려해 시간복잡도가 낮은 알고리즘을 택해야 한다
• 문제에서 일반적으로 모든 간선을 고려한다면 두가지 알고리즘 모두 사용할 수 없다.
• 문제 최적화를 위해 행성간의 거리를 주목해야하는데 행성간의 거리는 아래처럼 정의되어 있다.

  dist = MIN(|x1-x2|, |y1-y2|, |z1-z3|)

• 위를 통해서 우리는 각 노드에 x, y, z 좌표에 대해 따로 정렬을 수행하고 인접한 노드끼리의 거리만 구해서 간선 후보군에 넣어주게 되면 후보 간선수는 최대 (10만-1)*3 = 30만 개가 되고 이는 크루스칼 알고리즘을 적용할 수 있다.
• 자세한 구현은 소스코드를 참조

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;

    public static int N;
    public static Point[] X, Y, Z;
    public static int[] parent;

    //(노드 번호, 좌표값), (노드 번호, 노드 번호)
    public static class Point {
        int a, b;
        public Point(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    //(거리, (a좌표, b좌표))
    public static class Planet {
        int d;
        Point p;

        public Planet(int d, Point p) {
            this.d = d;
            this.p = p;
        }
    }

    //Union-Find
    public static int find(int a) {
        if (parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        X = new Point[N];
        Y = new Point[N];
        Z = new Point[N];
        parent = new int[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            X[i] = new Point(i, Integer.parseInt(st.nextToken()));
            Y[i] = new Point(i, Integer.parseInt(st.nextToken()));
            Z[i] = new Point(i, Integer.parseInt(st.nextToken()));
            parent[i] = i;
        }
    }


    public static void solve() throws IOException {
        //0. 모든 좌표값들 정렬해주기
        Comparator<Point> comp = (p1, p2) -> p1.b - p2.b;
        Arrays.sort(X, comp);
        Arrays.sort(Y, comp);
        Arrays.sort(Z, comp);

        //1. 최소 거리 좌표들 모두 후보군에 넣어주기
        List<Planet> cands = new ArrayList<>();
        for (int i = 0; i < N-1; i++) {
            cands.add(new Planet(Math.abs(X[i+1].b - X[i].b), new Point(X[i].a, X[i+1].a)));
            cands.add(new Planet(Math.abs(Y[i+1].b - Y[i].b), new Point(Y[i].a, Y[i+1].a)));
            cands.add(new Planet(Math.abs(Z[i+1].b - Z[i].b), new Point(Z[i].a, Z[i+1].a)));
        }
        cands.sort((p1, p2) -> p1.d - p2.d);

        //2. 크루스칼 알고리즘 시작
        long result = 0;
        for (Planet cand : cands) {
            if (find(cand.p.a) != find(cand.p.b)) {
                union(cand.p.a, cand.p.b);
                result += (long) cand.d;
            }
        }
        bw.write(result + "\n");
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}