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

in Algorithm on 그래프 이론

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

풀이

최소 신장 트리를 구하는 문제이다.

정점을 다 연결해야 하는데 이미 연결된 선이 주어진다.

이미 연결된 선은 가중치를 0으로 두고 계산했다.

크루스칼과 프림 알고리즘이 있는데 프림 알고리즘을 사용해봤다.

프림 알고리즘은 하나의 정점에서 연결된 간선들 중에서 하나씩 선택하면서 최소신장트리를 찾는 알고리즘이다

1. 임의 정점을 하나 선택해서 시작한다.

2. 선택한 정점과 인접하는 정점들 중 최소 비용의 간선과 연결된 정점을 선택한다.

3. 모든 정점이 선택될때까지(정점의 개수 - 1개의 간선이 선택될때까지) 1, 2번과정을 반복한다.

pq에 방문하지 않은 점들을 넣고 가중치가 작은 순으로 PriorityQueue를 이용해 더해주었다.

연결된 선의 수가 정점의 수 - 1이 될때까지 더해주면 모두 연결된 것이다.

메모리: 61740KB

시간: 428ms

언어: Java 11

코드

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

public class Main {
    static class Node implements Comparable<Node> {
        int point;
        double dist;

        public Node(int point, double dist) {
            this.point = point;
            this.dist = dist;
        }

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

    static ArrayList<ArrayList<Node>> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] cord = new int[N + 1][2];
        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            cord[i][0] = Integer.parseInt(st.nextToken());
            cord[i][1] = Integer.parseInt(st.nextToken());
        }

        list = new ArrayList<>();
        for (int i = 1; i <= N + 1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < N + 1; j++) {
                if (i != j) {
                    double dist = Math
                            .sqrt(Math.pow((cord[i][0] - cord[j][0]), 2) + Math.pow((cord[i][1] - cord[j][1]), 2));
                    list.get(i).add(new Node(j, dist));
                }
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list.get(x).add(new Node(y, 0));
            list.get(y).add(new Node(x, 0));
        }

        prim(1, N);
    }

    private static void prim(int start, int n) {
        boolean[] visit = new boolean[n + 1];

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        double total = 0;
        int pick = 0;
        while (pick < n) {
            Node node = pq.poll();

            if (visit[node.point]) {
                continue;
            }

            visit[node.point] = true;
            total += node.dist;
            pick++;

            for (Node next : list.get(node.point)) {
                if (!visit[next.point]) {
                    pq.add(next);
                }
            }
        }

        System.out.printf("%.2f", total);
    }

}