Union-Find, Kruskal 정리

union - find

장점 : 만약 여러 개의 노드 무리들이 있다고 가정했을 때, 2개의 노드를 선택했을 때 그 노드들이 연결이 되어있는지 찾기가 용이하다.

예시 문제 - 프로그래머스 호텔 방배정

https://school.programmers.co.kr/learn/courses/30/lessons/64063

 

최소 스패닝 트리(MST)는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

 

입력으로 주어지는 그래프는 하나의 연결 그래프임이 보장된다.

이때 프림과 크루스칼 적용 → 주목적이 최소 스패닝 트리를 만드는 것

 

Kruskal → 시간복잡도O(ElogE)

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

class Edge implements Comparable<Edge>{
	int from;
	int to;
	int cost;
	
	public Edge(int from, int to, int cost) {
		super();
		this.from = from;
		this.to = to;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return (this.cost - o.cost);
	}
	
}
public class Solution {

	
	static int v;
	static int e;
	static int[] parents;
	static ArrayList<Edge> edgeList;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st= new StringTokenizer(br.readLine());

		v= Integer.parseInt(st.nextToken());
		e= Integer.parseInt(st.nextToken());
		edgeList= new ArrayList<>();
	
		make();

		for (int i = 0; i < e; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			edgeList.add(new Edge(from, to, cost));
		}
		
		Collections.sort(edgeList);

		long sumCost=0;
		int cnt=0;
		for (int i = 0, size = edgeList.size(); i < size; i++) {
			Edge now = edgeList.get(i);
			
			if(union(now.to, now.from)) {
				sumCost += (long)now.cost;
				cnt++;
			}

		}

		//이때 cnt의 값이 무조건 정점개수 - 1 이어야한다.
		System.out.println(sumCost);
			
		
	}
	static void make() { 

		parents = new int[v+1];
		for (int i = 1; i <= v; i++) { 
			parents[i] = i;
		}
	}

	static int find(int a) { 
		if (parents[a] == a)
			return a;

		return parents[a] = find(parents[a]);
	}

	static boolean union(int a, int b) { 
		int aRoot = find(a);
		int bRoot = find(b);

		if (aRoot == bRoot)
			return false;

		if(aRoot!=bRoot){
			if(aRoot<bRoot) parents[bRoot]=aRoot;
			else parents[aRoot] = bRoot;
		}
		return true;
	}

	

}