[백준] 1197 최소 스패닝 트리 - 최소신장트리(Minimum Spanning Tree, MST) + 크루스칼(Kruskal) JAVA

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

1197번: 최소 스패닝 트리

코드설명

최소신장트리(Minimum Spanning Tree, MST) + 크루스칼(Kruskal) 문제입니다.

 

크루스칼 알고리즘을 활용하여 최소한의 비용으로 신장 트리를 찾는 문제입니다

.

신장 트리란 그래프 상에서 모든 노드가 사이클 없이 연결된 부분 그래프를 의미합니다.

최소 신장 트리란 그래프 상에서 모든 노드가 사이클 없이 연결된 부분 그래프이면서 모든 정점이 최소 간선의 햡으로 연결된 부분 그래프입니다.

 

이때 최소 신장트리를 찾기 위해 Collections.sort를 간선의 무게에 맞추어서 정렬해줍니다.

싸이클을 판별해내기 위해 유니온파인드(Union-Find)를 통해 판별합니다.

코드

import java.util.*;
 
public class Main {
	public static int v,e;
	public static int[] parent = new int[100001];
	public static ArrayList<Edge> edges = new ArrayList<>();
	public static int result = 0;
	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	v = sc.nextInt();
    	e = sc.nextInt();
    	
    	for(int i=1; i<=v; i++) {
    		parent[i] = i;
    	}
    	
    	for(int i=0;i<e;i++) {
    		int a = sc.nextInt();
    		int b = sc.nextInt();
    		int cost = sc.nextInt();
    		edges.add(new Edge(cost, a, b));
    	}
    	
    	Collections.sort(edges);
    	
    	for(int i=0;i<edges.size();i++) {
    		int cost = edges.get(i).distance;
    		int a = edges.get(i).nodeA;
    		int b = edges.get(i).nodeB;
    		//사이클이 발생하지 않는 경우에만 집합에 포함
    		if( findParent(a) != findParent(b) ) {
    			unionParent(a,b);
    			result += cost;
    		}
    	}
    	System.out.println(result);
    }
    
    public static int findParent(int x) {
    	if(x == parent[x]) return x;
    	return parent[x] = findParent(parent[x]);
    }
    
    public static void unionParent(int a, int b) {
    	a = findParent(a);
    	b = findParent(b);
    	if( a < b ) parent[b] = a;
    	else parent[a] = b;
    }
}
 
class Edge implements Comparable<Edge>{
	int distance;
	int nodeA;
	int nodeB;
	Edge(int distance, int nodeA, int nodeB){
		this.distance = distance;
		this.nodeA = nodeA;
		this.nodeB = nodeB;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		if(this.distance < o.distance) {
			return -1;
		}
		return 1;
	}	
}