백준 16398 (행성 연결) - java

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

16398번: 행성 연결

크루스컬 알고리즘을 사용하여 MST를 만드는 문제이다. 정답의 범위가 long일 수 있기 때문에 주의가 필요하다.

무방향 그래프이기 때문에 중복되는 입력에 대한 처리를 통해 시간을 아끼는 것 또한 방법이다.

 

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

public class Main {
    static int n = 0;
    static int[] root;


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

        int[][] graph = new int[n*n+1][3];
        root = new int[n+1];

        int idx = 1;
        for(int i=1;i<=n;i++)
        {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=1;j<=n;j++)
            {
                int tmp = Integer.parseInt(st.nextToken());

                if(i < j) {
                    graph[idx][0] = i;
                    graph[idx][1] = j;
                    graph[idx][2] = tmp;
                    idx = idx + 1;
                }
            }
        }

        Arrays.sort(graph,1,idx,(x,y) -> x[2] - y[2] );
        
        for(int i=1;i<=n;i++)
        {
            root[i] = i;
        }

        long cost = 0;
        for(int i=1; i < idx;i++)
        {
            if(find(graph[i][0]) != find(graph[i][1]))
            {
                cost += graph[i][2];
                union(graph[i][0],graph[i][1]);
            }
        }
        System.out.println(cost);

        br.close();
    }


    static int find(int x)
    {
        if(x == root[x])
            return x;

        else{
            return root[x] = find(root[x]);
        }
    }


    static void union(int x,int y)
    {
        x = find(x);
        y = find(y);

        if(x < y)
        {
            root[y] = x;
        }

        else{
            root[x] = y;
        }
    }
}