백준 2887번 : 행성 터널 [자바]

 

🧫 문제 분석

 

✔️ 출처

행성 터널 플래티넘 5

 

📖 문제

 

 

최소 비용 MST 문제

크루스칼로 풀면된다.

 

문제에서 x길이, y길이, z길이중 가장 작은 값을 비용으로 사용하고

터널 N-1개를 생성한다. 이때 연결에 필요한 최소 비용 구하기

 

어떤 수열에서 오름차순 정렬시 자신의 인접 수가 가장 자신과 가까운 값이 된다. 

 

x, y, z 각각 기준으로 정렬하고

인접 노드와의 거리를 구한후 우선순위 큐에 저장한다. 

 

우선순위 큐에서 가장 작은 비용의 터널 건설 정보를 꺼내서 

union-find set 을 사용하여 터널의 건설 여부를 체크하고 

union으로 터널을 건설한 두 행성을 합치고

 

최종 비용을 더한다. 

 

 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Main {

    static class Point implements Comparable<Point>{
        int v;
        int idx;

        public Point(int v, int idx) {
            this.v = v;
            this.idx = idx;
        }

        @Override
        public int compareTo(Point o) {
            return Long.compare(v, o.v);
        }
    }

    static int[] parent;

    static PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Long.compare(o1[0], o2[0]));
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        parent = IntStream.range(0, n).toArray();
        Point[][] planets = new Point[3][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            
            // 좌표값, i번째 행성
            planets[0][i] = new Point(x, i); 
            planets[1][i] = new Point(y, i);
            planets[2][i] = new Point(z, i);

        }

        // 각 좌표의 값들을 정렬하고 터널(엣지) 건설 정보를 생성하여 우선순위 큐에 삽입
        for (int i = 0; i < 3; i++) {
            Arrays.sort(planets[i]);
            createEdge(n, planets[i]);
        }

        long answer = 0;
        int cnt = 0;
        while (!pq.isEmpty()) {
            if (cnt == n-1) break;

            int[] info = pq.poll();
            int v1 = info[1];
            int v2 = info[2];

            if (find(v1) != find(v2)) {
                union(v1,v2);
                answer += info[0];
                cnt++;
            }
        }

        System.out.println(answer);
    }


    private static void union(int a, int b) {

        a = find(a);
        b = find(b);

        if (a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }

    private static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    private static void createEdge(int n, Point[] point) {
        for (int i = 1; i < n; i++) {
            Point p1 = point[i];
            Point p2 = point[i - 1];

            pq.add(new int[]{Math.abs(p1.v - p2.v), p1.idx, p2.idx});

        }
    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1.