[BOJ] 행성 터널

[2887] 행성 터널

www.acmicpc.net/problem/2887

 

Solution

• 행성들을 잇는 최소 간선 트리를 만드는 간단한 문제이다.
• 처음에는 행성을 이을 수 있는 모든 간선을 미리 구해서 푸는 방식으로 접근했는 데 메모리 초과로 틀렸다.
• int x, y, z -> 12byte이고,  행성 개수가 최대 10만개이기 때문에 (10만 * 10만 / 2) = 약 50억으로 12byte * 50억이라하면 메모리가 초과될 수 밖에 없었다.
• 문제를 다시 한 번 살펴보면 행성의 x, y, z 좌표를 각각 비교해서 최소 비용을 구하는 것이므로 모든 행성간의 비용을 계산할 필요 없이 좌표 별로 오름차순으로 정렬한 뒤 바로 옆 행성만 비교하면 된다.
• 예를들어 행성 A, B, C의 x좌표를 기준으로 정렬한 결과가 B(3) - A(5) - C(9)라고 하면 바로 옆에 있는 행성과의 거리가 가장 적기 때문에 B-A, A-C 만 pq에 저장하면된다.

 

 

소스코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static int n;
    static int[] p;
    static List<Node> list;
 
    static class Edge implements Comparable<Edge> {
        private int start;
        private int end;
        private int val;
 
        public Edge(int start, int end, int val) {
            this.start = start;
            this.end = end;
            this.val = val;
        }
 
        @Override
        public int compareTo(Edge o) {
            return this.val - o.val;
        }
    }
 
    static class Node {
        private int x;
        private int y;
        private int z;
        private int num;
 
        public Node(int x, int y, int z, int num) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.num = num;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = stoi(br.readLine());
 
        p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
 
        list = new ArrayList<>();
        int x, y, z;
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            x = stoi(st.nextToken());
            y = stoi(st.nextToken());
            z = stoi(st.nextToken());
 
            list.add(new Node(x, y, z, i));
        }
 
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        Collections.sort(list, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.x - o2.x;
            }
        });
        for (int i = 0; i < list.size() - 1; i++) {
            pq.add(new Edge(list.get(i).num, list.get(i + 1).num, Math.abs(list.get(i).x - list.get(i + 1).x)));
        }
 
        Collections.sort(list, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.y - o2.y;
            }
        });
        for (int i = 0; i < list.size() - 1; i++) {
            pq.add(new Edge(list.get(i).num, list.get(i + 1).num,Math.abs(list.get(i).y - list.get(i + 1).y)));
        }
 
        Collections.sort(list, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.z - o2.z;
            }
        });
        for (int i = 0; i < list.size() - 1; i++) {
            pq.add(new Edge(list.get(i).num, list.get(i + 1).num, Math.abs(list.get(i).z - list.get(i + 1).z)));
        }
 
        int answer = 0;
        int count = 0;
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            if (find(edge.start) != find(edge.end)) {
                union(edge.start, edge.end);
                answer += edge.val;
                count++;
            }
            if (count == n - 1) {
                break;
            }
        }
 
        System.out.println(answer);
    }
 
    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            p[b] = a;
        }
    }
 
    private static int find(int a) {
        if (p[a] == a) {
            return a;
        }
        return p[a] = find(p[a]);
    }
 
    private static int stoi(String s) {
        return Integer.parseInt(s);
    }
}