백준 2887 행성 터널 java

문제 소개 www.acmicpc.net/problem/2887

내용

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

아이디어

• n-1 개의 간선을 선택해서 최소 비용 신장 트리를 만드는 것과 동일한 문제로 생각된다.
• 최소 비용 신장 트리를 만드는 데 사용하는 알고리즘은 크루스칼과 프림이 있다.
• 크루스칼의 시간복잡도는 eloge 이다.
• 정점의 수가 100,000이다. 고로 edge의 총 개수는 정점 제곱과 비례하니까 100,000 제곱개 임을 알 수 있었다.
• 크루스칼로 풀면 시간 초과가 날 것 같다고 생각했다.
• 그러면 프림으로 도전해보자. 프림의 알고리즘의 시간복잡도는 n^2 이니까. 그나마 크루스칼 보다 빠르다고 생각했다.

실제 풀이 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        List<Planet> planets = new ArrayList<>();
        for (int i = 0; i < planetCount; i++) {
            String[] split = br.readLine().split(" ");
            planets.add(new Planet(i, Integer.parseInt(split[0]), Integer.parseInt(split[1]), Integer.parseInt(split[2])));
        }

        boolean[] visited = new boolean[planetCount];

        Queue<Planet> queue = new LinkedList<>();
        queue.add(planets.get(0));

        int answer = 0;
        while(!queue.isEmpty()){
            Planet current = queue.poll();
            visited[current.index] = true;

            Planet next = null;
            int minCost = Integer.MAX_VALUE;
            for (Planet planet : planets) {
                if (visited[planet.index]) continue;
                if (minCost > current.getCost(planet)){
                    minCost = current.getCost(planet);
                    next = planet;
                }
            }

            if (next != null) {
                queue.add(next);
                answer += minCost;
            }
        }

        System.out.println(answer);
    }

    static class Planet {
        int index;
        int x;
        int y;
        int z;

        public Planet(int index, int x, int y, int z) {
            this.index = index;
            this.x = x;
            this.y = y;
            this.z = z;
        }

        public int getCost(Planet other) {
            return Math.min(Math.min(Math.abs(this.x - other.x), Math.abs(this.y - other.y)), Math.abs(this.z - other.z));
        }
    }
}

 

결과

혹시나 했지만 100,000^2은 역시나 시간초과가 발생한다. 그러면 단순 크루스칼, 프림 알고리즘으로 해결하는 것이 아니라고 생각이 들었다. 

 

해결 방법 - 2

아이디어

• 해결 방법 -2 는 steady-coding.tistory.com/117 를 보고 알았다.
• 제 아이디어에서 문제점은 모든 행성들 사이를 간선으로 만들어질 수 있다는 점이 문제라고 생각이 든다.
• 모든 행성을 x축만 있다고 생각하고 x축으로 정렬했을 시 예로 0, 3, 5, 8, 10으로 정렬되었다면 내가 고려해야 하는 간선은 0-3, 3-5, 5-8, 8-10만 고려하면 되었다는 것이다. 
• 마찬가지로 y축, z축도 동일하게 간선을 만들게되면 대략 300,000 간선이 나오고 이 간선을 가지고 크루스칼 알고리즘을 수행해보자.

실제 풀이 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        List<Planet> planets = new ArrayList<>();
        for (int i = 0; i < planetCount; i++) {
            String[] split = br.readLine().split(" ");
            planets.add(new Planet(i, Integer.parseInt(split[0]), Integer.parseInt(split[1]), Integer.parseInt(split[2])));
        }

        List<Tunnel> tunnels = new ArrayList<>();

        planets.sort(Comparator.comparingInt(p -> p.x));
        for (int i = 0; i < planets.size() - 1; i++) {
            Planet from = planets.get(i);
            Planet to = planets.get(i + 1);
            tunnels.add(new Tunnel(from.index, to.index, Math.abs(from.x - to.x)));
        }

        planets.sort(Comparator.comparingInt(p -> p.y));
        for (int i = 0; i < planets.size() - 1; i++) {
            Planet from = planets.get(i);
            Planet to = planets.get(i + 1);
            tunnels.add(new Tunnel(from.index, to.index, Math.abs(from.y - to.y)));
        }

        planets.sort(Comparator.comparingInt(p -> p.z));
        for (int i = 0; i < planets.size() - 1; i++) {
            Planet from = planets.get(i);
            Planet to = planets.get(i + 1);
            tunnels.add(new Tunnel(from.index, to.index, Math.abs(from.z - to.z)));
        }

        Collections.sort(tunnels);

        int[] cycleTable = new int[planetCount];
        for (int i = 0; i < planetCount; i++) {
            cycleTable[i] = i;
        }

        int answer = 0;
        for (Tunnel tunnel : tunnels) {
            int parentFrom = getParent(cycleTable, tunnel.from);
            int parentTo = getParent(cycleTable, tunnel.to);

            if (parentFrom != parentTo) {
                answer += tunnel.cost;
                union(cycleTable, tunnel.from, tunnel.to);
            }
        }

        System.out.println(answer);
    }

    private static void union(int[] cycleTable, int from, int to) {
        int parentFrom = getParent(cycleTable, from);
        int parentTo = getParent(cycleTable, to);

        if (parentFrom > parentTo) cycleTable[parentFrom] = parentTo;
        else cycleTable[parentTo] = parentFrom;
    }

    private static int getParent(int[] cycleTable, int child) {
        if (cycleTable[child] == child) return child;
        return getParent(cycleTable, cycleTable[child]);
    }

    static class Planet {
        int index;
        int x;
        int y;
        int z;

        public Planet(int index, int x, int y, int z) {
            this.index = index;
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }

    static class Tunnel implements Comparable<Tunnel> {
        int from;
        int to;
        int cost;

        public Tunnel(int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }

        @Override
        public int compareTo(Tunnel o) {
            return Integer.compare(this.cost, o.cost);
        }
    }
}

결과