[Java 백준] 2887 행성터널 플래티넘5

🔗 문제링크 🔗

2887번: 행성 터널

---

🌟 생각 흐름 🌟

오랜만에 그래프 문제 푸니까 재미있었다.

1. 모든 행성의 경우에 대해서 계산하기 ->   100,000 * 99,999 /2 하니까 메모리 에러가 났다.

2. 고민을 하다가 메모리 초과가 난경우에 대해서 생각을 해봤다. 문제를 다시 읽다 보니 터널생성에는 x, y, z 중 제일 작은 차를 이용한다. 즉 x, y, z의 제일 작은 값들만 비교하면 다른 값들은 의미가 없다는 생각이 들었다. 따라서 x, y, z를 기준으로 각각 정렬을 하여 앞뒤로 현재 기준인 좌표의 차를 구해서 저장한다(그 값이 터널의 min값이다).

그 이후에는 일반 크루스칼 알고리즘 풀이와 동일하게 풀었다. 

x,y,z를 기준으로 정렬하는 게 빨리 떠올라서 메모리 초과를 빨리 해결할 수 있었던 거 같다. 

알고리즘을 빨리 푸는건 그날의 운일까 실력일까.. (오늘은 운이 좋았던 게 아닐까)

---

🍳 코드 🍳

 

package 백준.graph.mst;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//크루스칼 풀이 과정
public class boj_2887_행성터널 {
    private static class Tunnel implements Comparable<Tunnel> {
        int start, end, cost;

        public Tunnel(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
        @Override
        public int compareTo(Tunnel o) {
            return cost - o.cost;
        }
    }

    private static int[] parents;
    private static final PriorityQueue<Tunnel> allTunnel = new PriorityQueue<>();

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

        int n = Integer.parseInt(br.readLine());
        int[][] planets = new int[n][4]; //x,y,z
        parents = new int[n];
        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            planets[i][3] = i;//idx
            planets[i][0] = Integer.parseInt(st.nextToken());
            planets[i][1] = Integer.parseInt(st.nextToken());
            planets[i][2] = Integer.parseInt(st.nextToken());
        }


        //x,y,z에 대해서 정렬 [[이렇게 하지 않고 x,y,x를 따로 입력 받아서 정렬하는 방법도 있음]]
        for (int i = 0; i < 3; i++) {
            int now = i;
            Arrays.sort(planets, Comparator.comparingInt(o -> o[now]));
            for (int j = 0; j < n - 1; j++) {
                int min = Math.abs(planets[j][i] - planets[j + 1][i]);
                allTunnel.add(new Tunnel(planets[j][3], planets[j + 1][3], min));
            }
        }


        long minDistance = 0;
        while (!allTunnel.isEmpty()) {
            Tunnel poll = allTunnel.poll();
            int aParent = findParent(poll.start);
            int bParent = findParent(poll.end);
            if (aParent == bParent) continue;
            minDistance += poll.cost;
            unionParents(aParent, bParent);
        }
        System.out.println(minDistance);

    }

    static int findParent(int x) {
        if (parents[x] == x) return x;
        return parents[x] = findParent(parents[x]);
    }

    static void unionParents(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a < b) parents[b] = a;
        else parents[a] = b;
    }
}