[백준][트리] 1197 최소 스패닝 트리(크루스칼 알고리즘)

이 문제는 최소 스패닝 트리를 구현하는 방법중 크루스칼 알고리즘을 이용하여 구현하면 된다. 

크루스칼 알고리즘은 그래프 사이 연결의 최소비용을 찾으면 된다. 

간선을 비용순으로 정렬하고,

가장작은 비용이 들어가는 간선을 사이클이 생기지 않는 순서대로 선택하면된다. 

간선 사이의 사이클은 union, find 연산을 이용하여 처리한다. 

	import java.util.Arrays;
	import java.util.Comparator;
	import java.util.Scanner;
	/**
	* 백준, 1197 최소 스패닝 트리 크루스칼 알고리즘
	*
	* @author User
	*
	*/
	public class Main {
	static int V;
	static int E;
	static int[][] edges;
	static int[] parent;
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	V = sc.nextInt();
	E = sc.nextInt();
	parent = new int[V + 1];
	for(int i = 1; i <= V; i++)
	parent[i] = i;
	edges = new int[E][3];
	for (int i = 0; i < E; i++) {
	int from = sc.nextInt();
	int to = sc.nextInt();
	int cost = sc.nextInt();
	edges[i][0] = from;
	edges[i][1] = to;
	edges[i][2] = cost;
	}
	sc.close();
	Arrays.sort(edges, new Comparator<int[]>() {
	@Override
	public int compare(int[] a, int[] b) {
	return a[2] >= b[2] ? 1 : -1;
	}
	});
	int sum = 0;
	int edgeCount = 0;
	for (int i = 0; i < E; i++) {
	int from = edges[i][0];
	int to = edges[i][1];
	int cost = edges[i][2];
	if (find(from) != find(to)) {
	union(from, to);
	sum += cost;
	if (++edgeCount == V - 1)
	break;
	}
	}
	System.out.println(sum);
	}
	public static int find(int x) {
	if (x == parent[x])
	return x;
	int root = find(parent[x]);
	parent[x] = root;
	return root;
	}
	public static void union(int x, int y) {
	x = find(x);
	y = find(y);
	parent[y] = x;
	}
	}

view raw Problem1197.java hosted with ❤ by GitHub

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