[백준] 우주신과의 교감 1774번 자바

 

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

 

기본적인 MST 문제입니다.

 

최소신장트리

그래프의 모든 정점을 사이클 없이 잇는 트리에서 간선의 가중치의 합이 최소가 되는 트리

 

크루스칼 알고리즘

간선을 하나씩 늘려가면서 이어줍니다.

 

 

[풀이한 코드]

package mst;

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

public class B1774 {
    static class Node {
        int x;
        int y;
        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static class Edge implements Comparable<Edge> {
        int a;
        int b;
        double dist;
        public Edge(int a, int b, double dist) {
            this.a = a;
            this.b = b;
            this.dist = dist;
        }

        @Override
        public int compareTo(Edge o) {
            return Double.compare(this.dist, o.dist);
        }
    }
    static int[] parents;
    static Node[] nodes;
    static int N;
    static int M;

    public static void main(String[] args) 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());
        nodes = new Node[N + 1];
        parents = new int[N + 1];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            nodes[i + 1] = new Node(x, y);
            parents[i + 1] = i + 1;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            unionParent(a, b);
        }

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                double cost = Math.sqrt(Math.pow(nodes[i].x - nodes[j].x, 2) + Math.pow(nodes[i].y - nodes[j].y, 2));
                pq.add(new Edge(i, j, cost));
            }
        }
        double cost = 0;
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            if (findParent(edge.a) != findParent(edge.b)) {
                unionParent(edge.a, edge.b);
                cost += edge.dist;
            }
        }
        System.out.printf("%.2f", cost);
    }

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

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

 

 

[시간복잡도]

1. 이미 연결된 간선 처리

- M개의 이미 연결된 간선을 처리합니다.

- 이때, Union Find 알고리즘을 사요했습니다. 해당 알고리즘은 O(1)에 가까운 시간복잡도를 갖습니다.

 

 2. 모든 노드 간 거리를 우선순위 큐에 삽입

- 우선순위 큐에 삽입하는 연산: O(logN)

-> 이중 반복문을 돌리며 우선순위 큐에 삽입하는 연산: O(N^2 logN)

 

3. 크루스칼 알고리즘

- 우선순위 큐에서 poll() 연산: O(logN)

- unionParent() 연산: O(1) 에 가까움

-> N^2 번 수행

-> O(N^2 logN)

 

따라서 최종 시간복잡도는 O(N^2 logN) 입니다.

 

[기억하자]

1. inner class 의 비교 방법

- Comparable<Edge> 를 implements하기

- @Override public int compareTo() 구현

static class Edge implements Comparable<Edge> {
    int a;
    int b;
    double dist;
    public Edge(int a, int b, double dist) {
        this.a = a;
        this.b = b;
        this.dist = dist;
    }

    @Override
    public int compareTo(Edge o) {
        return Double.compare(this.dist, o.dist);
    }
}

 

2. 제곱할 때 x * x는 오버플로 발생 가능성이 있기 때문에 Math.pow() 사용하기

- 단, 반환값은 항상 double이다.

- Math.pow(x, 2) 를 하면 x의 2제곱

 

3. 출력할 때 소수점 2번째 자리까지 반올림하기

- System.out.printf("%.2f", 수);