[백준 2887] - 행성터널(Java)[플레5]

문제

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

2887번: 행성 터널

 

문제 풀이

처음에 N개의 행성을 받아서 Prim 알고리즘을 사용해서 구현했었다.

그렇게 하다보니 메모리초과가 발생했다.

도저히 이유를 알지 못해서 질문게시판을 참고했다.

정점의 개수가 N개고, 최대 입력개수가 100,000개인데 모든 행성간의 간선 정보를 포문으로 계산할 시 메모리 초과가 발생하는것이었고,

메모리초과를 해결하기 위해서 간선을 최적화해서 수를 줄여야 했다.

 

3차원의 평면이지만, 간선을 각각 2차원으로 낮춰서 (x,y) (y,z) (x,z) 각각의 간선을 구한다면 간선을 최적화 할 수 있다.

따라서 각 좌표 차원에 맞게 오름차순으로 정렬해서 인접한 정점의 거리를 구하고,

정점을 기준으로 뻗어나가는 점과 거리를 계산한 Node를 구해준다.

그 다음으론 우선순위 큐를 사용한 Prim 알고리즘을 사용해서 출발 정점에서 가까운 정점으로 방문하고,

방문한 노드에 대해서 비용을 계속해서 더해주면 끝이다.

전체 코드

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

public class Main {

    static int n;
    static BufferedReader br;
    static StringTokenizer st;

    static int answer = 0;
    static boolean[] visit;

    static PriorityQueue<Node> pq = new PriorityQueue<>();
    static List<Node>[] list;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        input();
        prim();
        System.out.print(answer);
    }

    public static void input() throws IOException {
        n = Integer.parseInt(st.nextToken());
        visit = new boolean[n];
        List<int[]> data = new ArrayList<>();
        list = new ArrayList[n + 1];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            data.add(new int[]{i, x, y, z});
            list[i] = new ArrayList<>();
        }
        for (int i = 1; i <= 3; i++) {
            int v = i;
            data.sort((o1, o2) -> (o1[v] - o2[v]));
            for (int j = 1; j < n; j++) {
                int[] p1 = data.get(j - 1);
                int[] p2 = data.get(j);
                int dis = Math.abs(p1[i] - p2[i]);
                list[p1[0]].add(new Node(p2[0], dis));
                list[p2[0]].add(new Node(p1[0], dis));
            }
        }
    }

    public static void prim() {
        pq.add(new Node(0, 0));
        while (!pq.isEmpty()) { //pq가 빌때까지 진행
            Node now = pq.poll();
            int curPosition = now.to;
            int value = now.value;
            if (visit[curPosition])
                continue;
            visit[curPosition] = true;
            answer += value;
            for (Node next : list[curPosition]) {
                if (!visit[next.to]) {
                    pq.add(next);
                }
            }
        }
    }

    static class Node implements Comparable<Node> {
        int to;
        int value;

        public Node(int to, int value) {
            this.to = to;
            this.value = value;
        }

        @Override
        public int compareTo(Node o) {
            return this.value - o.value;
        }
    }
}