[알고리즘]백준 1774_우주신과의 교감

백준 1774_우주신과의 교감

• 모든 좌표가 연결 + 최소 길이

• 매 좌표마다 다른 좌표와의 길이 배열 구하고 오름차순 정렬

• 기존에 연결되어있는 거 제외하고 길이 최소값인 좌표로 연결
  - union find로 연결되어있는지 확인 및 연결

• union find: 각 집단의 대표로 연결 여부 확인

• 최소 스패닝 트리: 모든 정점 연결 + 총 비용 최소, 싸이클 없음
  - KrusKal: 비용이 적은 간선부터 고르는 방식
  

/**
 * Edge : 간선, 두 좌표의 인덱스랑 거리 저장. 오름차순 정렬 설정.
 * find : 집단 대표 찾기 및  for union find
 * union : 두 좌표가 연결되어있는 지 집단 대표로 체크
 * edges: 좌표간의 Edge들을 길이기준 오름차순 정렬
 * parent 배열에 대표 저장, edges 순회 돌면서 연결안되어있으면 총 길이에 +
 */
import java.io.*;
import java.util.*;

public class Main {

    // 간선: 두 좌표 인덱스, 거리. 
    static class Edge implements Comparable<Edge> {
        int u, v; // 좌표 인덱스
        double w; // 길이

        Edge(int u, int v, double w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }

        // 거리 기준 오름차순 정렬. 거리는 실수범위 -> double 
        @Override
        public int compareTo(Edge o) {
            return Double.compare(this.w, o.w);
        }
    }

	// 대표 좌표 인덱스, rank 는 트리 높이 줄여 탐색 최적화용, 
    static int[] parent;
    static int[] rank;

    // x가 속한 그룹의 대표를 찾는 함수
    static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]); // 대표 갱신_경로 압축 + 반환
    }

    // a와 b를 같은 그룹으로 합치는 함수_연결 여부 확인 + rank 갱신
    // 이미 같은 그룹이면 false
    // 새롭게 합쳐졌으면 true
    static boolean union(int a, int b) {
        int ra = find(a); // a의 대표
        int rb = find(b); // b의 대표

        // 대표가 같으면, 이미 같은 그룹이면 합칠 필요 없음
        if (ra == rb) return false;

        // 더 낮은 트리를 높은 트리 대표에 붙여서 성능 개선
        if (rank[ra] < rank[rb]) {
            parent[ra] = rb;
        } else if (rank[ra] > rank[rb]) {
            parent[rb] = ra;
        } else {
            parent[rb] = ra;
            rank[ra]++;
        }

        return true;
    }

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

        // 정점 개수, 이미 연결된 간선 개수
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] x = new int[n + 1];
        int[] y = new int[n + 1];

        // 좌표 입력
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            x[i] = Integer.parseInt(st.nextToken());
            y[i] = Integer.parseInt(st.nextToken());
        }

        // union find초기화
        parent = new int[n + 1];
        rank = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            parent[i] = i; // 처음엔 자기 자신이 대표
        }

        // 이미 연결된 간선 먼저 반영
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            union(a, b);
        }

        // 모든 정점 쌍 사이의 거리로 간선 생성
        List<Edge> edges = new ArrayList<>();

		
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                long dx = x[i] - x[j];
                long dy = y[i] - y[j];
				
                // 거리 계산
                double dist = Math.sqrt(dx * dx + dy * dy);

                edges.add(new Edge(i, j, dist));
            }
        }

        // 거리 짧은 순으로 정렬
        Collections.sort(edges);

        double answer = 0.0;

        // 거리 짧은 순으로 체크
        for (Edge e : edges) {
            // 다른 그룹이면_연결 안되어있으면_ 연결 후 거리 +
            if (union(e.u, e.v)) {
                answer += e.w;
            }
        }

		// 소수점 둘째짜리까지 반올림 후 출력
        System.out.printf("%.2f\n", answer);
    }
}