[BaekJoon] 1774 우주신과의 교감 (Java)

1.  문제 링크

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

2.  문제

요약

• 황선자씨는 우주신과 교감을 할 수 있는 채널러인데, 우주신은 하나만 있는 것이 아니기 때문에 황선자씨는 매번 여럿의 우주신과 교감할 수 있습니다.
• 그러다 새로운 우주신들이 황선자씨를 이용하게 되었는데, 우주신들은 바로 황선자씨와 연결될 필요는 없습니다.
• 이미 황선자씨와 혹은 이미 우주신끼리 교감할 수 있는 우주신들이 있기 때문에 새로운 우주신들은 그 우주신들을 거쳐 황선자씨와 교감을 할 수 있습니다.
• 우주신들과의 교감은 우주신들과 황선자씨 혹은 우주신들끼리 이어진 정신적인 통로를 통해 이루어지는데, 이런 통로들이 길면 길수록 힘이 들기 때문에 통로가 긴 것을 황선자씨는 좋아하지 않습니다.
• 통로들의 길이는 2차원 좌표계상의 거리와 같습니다.
• 이미 황선자씨와 연결된, 혹은 우주신들과 연결된 통로들이 존재합니다.
• 새로 만들어야 할 정신적인 통로의 길이들이 합이 최소가 되게 통로를 만드는 문제입니다.
• 입력: 첫 번째 줄에 1,000보다 작거나 같은 우주신들의 개수 N과 이미 연결된 신들과의 통로의 개수 M이 주어지고 두 번째 줄부터 N개의 줄에 0보다 크거나 같고 1,000,000보다 작거나 같은 정수인 황선자를 포함하여 우주신들의 좌표 (X, Y)가 주어집니다. 그 밑으로 M개의 줄에는 이미 연결된 통로가 주어집니다.
  • 번호는 위의 입력받은 좌표들의 순서라고 생각하면 됩니다.
• 출력: 첫 번째 줄에 만들어야 할 최소의 통로 길이를 출력합니다. 출력은 소수점 둘째짜리까지 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static double answer;
    static int[][] locations, connected;
    static int[] parents;
    static PriorityQueue<Edge> edges;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        M = scanner.nextInt();
        locations = new int[N + 1][2];
        connected = new int[M + 1][2];
        for(int idx = 1; idx <= N; idx++) {
            int x = scanner.nextInt(), y = scanner.nextInt();
            locations[idx][0] = x;
            locations[idx][1] = y;
        }
        for(int idx = 0; idx < M; idx++) {
            int first = scanner.nextInt(), second = scanner.nextInt();
            connected[idx][0] = first;
            connected[idx][1] = second;
        }
    }

    static void solution() {
        answer = 0;
        parents = new int[N + 1];
        for(int loc = 1; loc <= N; loc++) parents[loc] = loc;

        int count = 0;
        for(int idx = 0; idx < M; idx++) {
            if(!isSameParents(connected[idx][0], connected[idx][1])) {
                union(connected[idx][0], connected[idx][1]);
                count++;
            }
        }

        makeEdge();
        while(count < N - 1) {
            Edge edge = edges.poll();
            int loc1 = edge.start, loc2 = edge.end;
            if(!isSameParents(loc1, loc2)) {
                union(loc1, loc2);
                count++;
                answer += edge.distance;
            }
        }

        System.out.println(String.format("%.2f", answer));
    }

    static void makeEdge() {
        edges = new PriorityQueue<>();
        for(int loc1 = 1; loc1 <= N; loc1++) {
            for(int loc2 = loc1 + 1; loc2 <= N; loc2++) {
                if(loc1 == loc2) continue;
                edges.offer(new Edge(loc1, loc2, getDistance(locations[loc1], locations[loc2])));
            }
        }
    }

    static double getDistance(int[] loc1, int[] loc2) {
        double distance = Math.sqrt(Math.pow(loc1[0] - loc2[0], 2) + Math.pow(loc1[1] - loc2[1], 2));
        return distance;
    }

    static int findParents(int loc) {
        if(loc == parents[loc]) return loc;
        return parents[loc] = findParents(parents[loc]);
    }

    static void union(int loc1, int loc2) {
        int parent1 = findParents(loc1), parent2 = findParents(loc2);
        if(parent1 != parent2) {
            if(parent1 < parent2) parents[parent2] = parent1;
            else parents[parent1] = parent2;
        }
    }

    static boolean isSameParents(int loc1, int loc2) {
        int parent1 = findParents(loc1), parent2 = findParents(loc2);
        if(parent1 == parent2) return true;
        return false;
    }

    static class Edge implements Comparable<Edge> {
        int start, end;
        double distance;
        public Edge(int start, int end, double distance) {
            this.start = start;
            this.end = end;
            this.distance = distance;
        }

        @Override
        public int compareTo(Edge e) {
            if(this.distance < e.distance) return -1;
            else if(this.distance > e.distance) return 1;
            else return 0;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 입력받은 황선자 및 우주신들의 좌표를 이용하여 각자 서로의 거리를 구하여 이를 그래프에서의 간선이라고 생각합니다. 이 간선들을 PriorityQueue에 거리에 대해 오름차순으로 넣습니다.
• 이미 연결된 통로들은 최소 스패닝 트리를 만들 때 이미 연결되어 있는 간선들이므로 우선 이 통로들은 연결시켜놓습니다.
• 총 N - 1개 이상의 간선이 될 때까지 PriorityQueue에 넣은 간선들을 하나씩 꺼내어 그래프에 연결시킵니다.
  • 이 때, 만약 사이클이 발생한다면 해당 간선은 건너뛰고 다음으로 거리가 짧은 간선을 선택하여 넣습니다.
• 이렇게 연결한 간선들의 거리들을 모두 더합니다.