백준 1197 : 최소 스패닝 트리 (Java)

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

1197번: 최소 스패닝 트리

 

도구를 늘리자! 알고리즘을 풀자!

 

최소 신장(스패닝) 트리를 만들어 보는 문제 '최소 스패닝 트리' 입니다.

 

최소 신장 트리를 만드는 알고리즘 프림과 크루스칼이 있는데요

 

저는 크루스칼 알고리즘을 통하여 구현해보았습니다.

 

makeSet, find, union 연산을 통해 서로소 집합으로 대표자를 찾아가면서 서로 연결시키는 방식입니다.

 

최소 신장 트리를 연습해보기 좋은 테케로 구성되어 있습니다 한번 풀어보세요!

 

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class 최소신장트리정답 {
    static long[] parent;
    static long[] rank;
     
    static class MST implements Comparable<MST>{
        long m;
        long p;
        long g;
        public MST(long m, long p, long g){
            this.m = m;
            this.p = p;
            this.g = g;
        }
		@Override
		public int compareTo(MST o) {
			// TODO Auto-generated method stub
			return (int) (this.g - o.g);
		}
    }
     
    public static void main(String[] args) {
         
        Scanner sc = new Scanner(System.in);

         
        
            int V = sc.nextInt();
            int E = sc.nextInt();
             
            parent = new long[V];
            rank = new long[V]; //초기 rank는 다0. rank에는 트리의 뎁스가 들어있음
             
            for(int i=0; i<V; i++)
                parent[i] = i;
             
            List<MST> node = new ArrayList<>();
            List<MST> ans = new ArrayList<>();
             
            //Make-Set
            for(int i=0; i<E; i++) {
                int m = sc.nextInt();
                int p = sc.nextInt();
                int g = sc.nextInt();
                node.add(new MST(m, p, g));
            }
            Collections.sort(node);
            
            int index = 0;
            long tg = 0;
            while(index < node.size()) {
                if(find(node.get(index).m-1) != find(node.get(index).p-1)) {
                    union(node.get(index).m-1,node.get(index).p-1);
                    tg += node.get(index).g;
                }
                index++;
            }
            System.out.println(tg);
        
    }
    //원소 x에 대해서. 대표자를 찾아주는 연산.
    static long find(long x) {
        if (parent[(int)x] == x)
            return x;
        parent[(int)x] = find(parent[(int)x]);
        return parent[(int)x];
             
    }
     
    static void union(long x, long y) {
        long px = find((int)x);
        long py = find((int)y);
        
        // 랭크(높이)가 더 큰 녀석 이 대표자가 된다면 랭크 서로소 집합의 높이가 더 커지지 않음
        if(rank[(int)px] > rank[(int)py])
            parent[(int)py] =  px;
        else if(rank[(int)px] < rank[(int)py])
            parent[(int)px] = py;
        else {
            parent[(int)px] = py;
            rank[(int)py]++;
        }
    }
}