[백준] 16398번 : 행성 연결

16398번: 행성 연결

---

[Kruskal, 최소 스패닝 트리]

문제에서 주어지는 인접 행렬의 정보를 받아 시작 정점(h), 도착 정점(tg) 그리고 비용(c)를 List에 담아 오름차순 정렬 후 크루스칼 알고리즘을 수행한다. 이 때 주의할 점은 비용은 최대 100,000,000이므로 비용을 더할 때 int가 아닌 long에 담아주도록 한다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static class Edge implements Comparable<Edge>{
        int h, tg, c;
        
        public Edge(int home, int t, int cc){
            h=home; 
            tg=t;
            c=cc;
        }
        
        @Override
        public int compareTo(Edge o) {
            return c - o.c;
        }
    }
    
    static List<Edge> list = new ArrayList<>();

    static int[] parent = new int[1001];
    
    static int getParent(int x){
        if(parent[x] == x) return x;
        return parent[x] = getParent(parent[x]);
    }
    static boolean findParent(int a, int b){
        a = getParent(a);
        b = getParent(b);

        return a == b? true:false;
    }
    static void unionParent(int a, int b){
        a = getParent(a);
        b = getParent(b);

        if(a<b) parent[b] = a;
        else parent[a] = b;
    }

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

        int n = Integer.parseInt(br.readLine());

        for(int i=1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            for(int j=1; j<=n; j++){
                int cost = Integer.parseInt(st.nextToken());

                if(i == j) continue;

                list.add(new Edge(i, j, cost));
            }
            parent[i] = i;
        }

        Collections.sort(list);
        long sum = 0L;

        for(Edge e : list){
            if(!findParent(e.h, e.tg)){
                sum += e.c;
                unionParent(e.h, e.tg);
            }
        }
        System.out.println(sum);
    }
}