[Algo] 백준 16398 행성 연결 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/16398

메모리 : 139400KB

시간 : 1156ms

언어 : Java 11

---

코드

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

public class Main {
    static class Node implements Comparable<Node> {
        int a, b, cost;

        Node(int a, int b, int cost) {
            this.a = a;
            this.b = b;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }

    static PriorityQueue<Node> pq = new PriorityQueue<>();
    static long mini;
    static int[] parent;
    static int N;

    public static <T> void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        mini = 0;
        parent = new int[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int c = Integer.parseInt(st.nextToken());
                pq.add(new Node(i, j, c));
            }
        }
        kruskal();
        System.out.print(mini);
    }

    private static void kruskal() {
        int cnt = 0;
        while (!pq.isEmpty()) {
            Node n = pq.poll();
            if (find(n.a) != find(n.b)) {
                union(n.a, n.b);
                mini += n.cost;
                cnt++;
            }
            if (cnt == N - 1)
                break;
        }
    }

    private static void union(int a, int b) {
        int x = find(a);
        int y = find(b);
        if (x <= y) {
            parent[y] = x;
        } else if (x > y) {
            parent[x] = y;
        }
    }

    private static int find(int num) {
        if (parent[num] == num) {
            return num;
        } else {
            return parent[num] = find(parent[num]);
        }
    }
}

풀이

크루스칼을 연습하기 위한 문제! 도시건설과 비슷하다.