2887 행성 터널

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

2887번: 행성 터널

고찰: 처음엔 크루스칼 알고리즘을 수행하기 위해 단순히 행성끼리 간선을 모두 연결하여 정렬하면 되겠다라고 생각한 순간 메모리 초과가 떴다..

행성의 최대 개수인 N이 10만인 것을 간과하고 N^2 으로 접근해서 그런 것 같다.

 

풀이: 문제의 조건 중 간선의 비용을 min (|x1 - x2|, |y1 - y2|, |z1 - z2|)로 계산한다는 것에 집중하자.

모든 간선을 연결하지 않고, 행성 간의 x, y, z 좌표 값을 기준으로 정렬하여 0~N - 1까지 간선을 만들어 연결하는 방식이다. 중복되는 간선이 있을 수 있지만 상관없다. 어차피 최소 비용만 만족하면 되기 때문이다.

이렇게 모든 간선을 만들면, nlogn * 3 + n의 시간이 들고 이후 만들어진 간선을 가지고 크루스칼 알고리즘을 수행하면 된다.

 

정답코드

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

class Edge implements Comparable<Edge>{
    int idx1, idx2; //(행성의 인덱스)
    long dist;
    public Edge(int idx1, int idx2, long dist) {
        this.idx1 = idx1;
        this.idx2 = idx2;
        this.dist = dist;
    }

    @Override
    public int compareTo(Edge e) {
        if(this.dist < e.dist){
            return -1;
        }
        else if(this.dist > e.dist){
            return 1;
        }
        return 0;
    }
}
class Planet {
    int idx; //행성의 좌표 (x, y, z 중 하나)
    int point;
    public Planet(int idx, int point){
        this.idx = idx;
        this.point = point;
    }
}
public class Main{
    public static int N;
    public static long answer;
    public static Planet[] x, y, z;
    public static int parents[];
    public static void _union(int a, int b){
        a = getParent(a);
        b = getParent(b);
        if(a < b)
            parents[b] = a;
        else
            parents[a] = b;
    }
    public static int getParent(int a){
        if(a == parents[a]){
            return a;
        }
        return parents[a] = getParent(parents[a]);
    }
    public static boolean find(int a, int b){
        a = getParent(a);
        b = getParent(b);
        if(a == b)
            return true;
        else
            return false;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        List<Edge> edges = new ArrayList<>();
        x = new Planet[N];  y = new Planet[N]; z = new Planet[N];
        parents = new int[N + 1];
        for(int i = 0; i < N; i++){
            parents[i] = i;
        }
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            x[i] = new Planet(i, Integer.parseInt(st.nextToken()));
            y[i] = new Planet(i, Integer.parseInt(st.nextToken()));
            z[i] = new Planet(i, Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(x, (p1, p2) -> p1.point - p2.point);
        for(int i = 0; i < N - 1; i++){
            edges.add(new Edge(x[i].idx, x[i + 1].idx, Math.abs(x[i].point - x[i + 1].point)));
        }
        Arrays.sort(y, (p1, p2) -> p1.point - p2.point);
        for(int i = 0; i < N - 1; i++){
            edges.add(new Edge(y[i].idx, y[i + 1].idx, Math.abs(y[i].point - y[i + 1].point)));
        }
        Arrays.sort(z, (p1, p2) -> p1.point - p2.point);
        for(int i = 0; i < N - 1; i++){
            edges.add(new Edge(z[i].idx, z[i + 1].idx, Math.abs(z[i].point - z[i + 1].point)));
        }
        Collections.sort(edges);
        for(Edge e : edges){
            if(!find(e.idx1, e.idx2)){
                _union(e.idx1, e.idx2);
                answer += e.dist;
            }
        }
        System.out.println(answer);
    }
}