[JAVA] 백준 - 1774 : 우주신과의 교감

문제 링크

1774번: 우주신과의 교감

 

풀이 ) MST - Kruskal

  입력으로 들어온 모든 점을 저장한 후 두 점 사이의 거리를 모두 구해서 최소힙에 넣어준다.

  이후 m개의 입력으로 들어온 선분을 먼저 이어주고 크루스칼 알고리즘을 적용하여 MST를 구했다.

 

코드 )

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

class Main {

    static int n, m;
    static Point[] points;
    static PriorityQueue<Node> pq;
    static int[] root;
    static int nPick = 1;

    public static void main(String[] args) throws IOException {
        input();
        kruskal();
    }

    static void kruskal() {
        double answer = 0;
        while(!pq.isEmpty()) {
            if(nPick == n) {
                break;
            }
            Node cur = pq.poll();
            if(find(cur.v1) != find(cur.v2)) {
                answer += cur.w;
                nPick++;
                union(cur.v1, cur.v2);
            }
        }
        System.out.printf("%.2f\n", answer);
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        root = new int[n];
        points = new Point[n];
        for(int i = 0; i < n; ++i) {
            root[i] = i;
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            points[i] = new Point(x, y);
        }
        // MinHeap
        pq = new PriorityQueue<>((o1, o2) ->
            Double.compare(o1.w, o2.w)
        );
        for(int i = 0; i < n-1; ++i) {
            for(int j = i+1; j < n; ++j) {
                int dx = points[i].x-points[j].x, dy = points[i].y-points[j].y;
                double tmp = Math.sqrt(1L*dx*dx+1L*dy*dy);	// long casting
                pq.offer(new Node(i, j, tmp));
            }
        }
        for(int i = 0; i < m; ++i) {
            st = new StringTokenizer(br.readLine(), " ");
            int v1 = Integer.parseInt(st.nextToken())-1;
            int v2 = Integer.parseInt(st.nextToken())-1;
            if(find(v1) != find(v2)) {
                nPick++;
                union(v1, v2);
            }
        }
    }

    static void union(int v1, int v2) {
        int root1 = find(v1);
        int root2 = find(v2);
        if(v1 < v2) {
            root[root2] = root1;
        } else {
            root[root1] = root2;
        }
    }

    static int find(int v) {
        if(root[v] == v) {
            return v;
        }
        return root[v] = find(root[v]);
    }

    static class Node {
        int v1, v2;
        double w;

        public Node(int v1, int v2, double w) {
            this.v1 = v1;
            this.v2 = v2;
            this.w = w;
        }
    }

    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

주의 )

  두 점 사이의 거리를 구할 때, 좌표의 범위가 [0, 1000000] 여서 차이를 제곱하면 Integer 범위를 벗어나기 때문에 Long으로 캐스팅해주는 작업이 필요하다.