[백준] BOJ1922 네트워크 연결 - MST(최소신장트리) - 크루스칼 알고리즘

MST (Minimum Spanning Tree) - Kruskal 알고리즘

MST 란 모든 노드를 최소 비용으로 연결하는 알고리즘인데, 아래의 조건을 만족해야 한다.

1) 싸이클이 없어야 하고

2) 모든 노드가 연결되어야 한다. 

이 때, a 노드에서 b 노드로 연결되어 있고, b 노드에서 c 노드로 연결되어 있다면, a 노드에서 c 노드로 연결되어 있다고 할 수 있다.

Kruskal 알고리즘

- 준비

// 간선을 가중치 기준으로 오름차순 정렬한다.

// 모든 점을 하나의 트리로 설정한다. (Union & Find 기법 사용)

- 시작

// 가중치가 작은 간선부터 하나씩 본다.

// 해당 간선을 그래프에 추가할 때 싸이클이 생기지 않는다면 해당 간선을 그래프에 추가한다.

백준 BOJ1922 문제를 풀기 위해 사용한 알고리즘 Kruskal 알고리즘 이고,

MST 알고리즘에 어려운 부분이 "싸이클이 생기지 않도록" 노드를 연결하는 것인데

Union & Find 기법으로 쉽게 해결할 수 있다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class BOJ1922 {
	
	static int[] parents;
	
	static class Edge{
		int v1;
		int v2;
		int w;
		public Edge(int v1, int v2, int w) {
			this.v1 = v1;
			this.v2 = v2;
			this.w = w;
		}
	}
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		int E = Integer.parseInt(br.readLine());
		
		Edge[] eList = new Edge[E];
		int v1, v2, w;
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			v1 = Integer.parseInt(st.nextToken());
			v2 = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());
			
			eList[i] = new Edge(v1, v2, w);
		}
		
		//- 준비
		// 간선을 가중치 기준으로 오름차순 정렬한다.
		Arrays.sort(eList, new Comparator() {
			@Override
			public int compare(Edge e1, Edge e2) {
				return e1.w - e2.w;
			}
		});
		
		// 모든 점을 하나의 트리로 설정한다. (Union & Find 기법 사용)
		parents = new int[N+1];
		for(int i=1; i<=N; i++) {
			parents[i] = i;
		}
		
		//- 시작
		int cost = 0;
		// 가중치가 작은 간선부터 하나씩 본다.
		for(Edge e : eList) {
			if( !isCycle(e) ) {
				// 해당 간선을 그래프에 추가할 때 싸이클이 생기지 않는다면 해당 간선을 그래프에 추가한다.
				addEdge(e);
				cost += e.w;
			}
		}
		
		System.out.println(cost);
	}
	
	public static void addEdge(Edge e) {
		int v1Root = findRoot(e.v1);
		int v2Root = findRoot(e.v2);
		
		parents[v1Root] = v2Root;
	}
	
	public static boolean isCycle(Edge e) {
		return findRoot(e.v1) == findRoot(e.v2) ? true : false;
	}
	
	public static int findRoot(int v) {
		if( parents[v] == v ) return v;
		
		parents[v] = findRoot(parents[v]);
		return parents[v];
	}
}