[백준] 16398번. 행성 연결(JAVA)

문제

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

---

풀이(15분)

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

public class Main {

    static int N;
    static int[] parent;

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

        N = Integer.parseInt(br.readLine());
        parent = new int[N+1];
        for(int i = 0; i <= N; i++){
            parent[i] = i;
        }

        PriorityQueue<Flow> pq = new PriorityQueue<>();

        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= N; j++){
                pq.add(new Flow(i, j, Integer.parseInt(st.nextToken())));
            }
        }

        long cost = 0;
        while(!pq.isEmpty()){
            Flow cur = pq.poll();
            if(union(cur.s, cur.e)){
                cost += cur.cost;
            }
        }

        System.out.println(cost);

    }

    public static boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if(rootA == rootB){
            return false;
        }
        if (rootA != rootB) { // 이미 같은 집합이 아닐 때만 병합
            if (rootA < rootB) { // 인덱스가 작은 것을 우선으로
                parent[rootB] = rootA;
            } else {
                parent[rootA] = rootB;
            }
        }

        return true;
    }

    static int find(int idx){
        if(idx == parent[idx]){
            return idx;
        }
        return parent[idx] = find(parent[idx]);
    }

    static class Flow implements Comparable<Flow>{
        int s;
        int e;
        int cost;

        public Flow(int s, int e, int cost){
            this.s = s;
            this.e = e;
            this.cost = cost;
        }

        @Override
        public int compareTo(Flow f){
            return this.cost - f.cost;
        }

    }
}

---

문제 풀이 전략

 

보자마자 최소 신장 트리를 떠올렸고, 크루스칼 알고리즘을 적용해야겠다고 생각했다.

[도구정리] 최소 신장 트리(MST) - 크루스칼(kruskal) 알고리즘