[백준 16398/JAVA] 행성 연결

문제

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

16398번: 행성 연결

풀이

가중치가 행렬로 주어졌다.
(x,x)를 기준으로 오른쪽 또는 왼쪽 값을 가중치로 받고 Kruskal로 MST를 구한다.

주의: 가중치가 1억 이상일 수 있음 -> 가중치 누적값 long으로 받아야 함

 

1<=N<=1,000
1<=i,j<=N
1<=가중치<=1억

 

가중치는 (노드 수-1) 만큼 누적될 수 있는데 노드 수는 최대 1,000개 -> int형은 정수를 약 20억까지밖에 표현하지 못 함. 따라서 정수형 변수로 long을 선언해야 함

코드

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

public class Main {
    static int[] parent;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        List<Edge> list = new ArrayList<>();
        long sum = 0;

        int N = Integer.parseInt(br.readLine());
        parent = new int[N+1];

        for(int i=1; i<N+1; i++){
            parent[i] = i;
        }

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<i; j++){
                int weight = Integer.parseInt(st.nextToken());
                list.add(new Edge(i, j, weight));
            }
        }

        Collections.sort(list);

        for(int i=0; i<list.size(); i++){
            Edge edge = list.get(i);
            if(!isSameParent(edge.x, edge.y)){
                union(edge.x, edge.y);
                sum += edge.weight;
            }
        }
        bw.write(sum+ " ");
        bw.close();
    }
    static boolean isSameParent(int x, int y){
        x = find(x);
        y = find(y);
        if(x != y)
            return false;
        return true;
    }
    static int find(int x){
        if(parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }
    static void union(int x, int y){
        x = find(x);
        y = find(y);
        if(x != y)
            parent[x] = y;
    }
}
class Edge implements Comparable<Edge> {
    int x, y, weight;

    Edge(int x, int y, int weight){
        this.x = x;
        this.y = y;
        this.weigh = weight;
    }

    public int compareTo(Edge e){
        return this.weight - e.weight;
    }
}