BOJ - 1197 ) 최소 스패닝 트리

 

---

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

1197번: 최소 스패닝 트리

---

MST를 구현하는 알고리즘에는 3가지가 있다.

1. Prim Algorithm

2. Kruskal Algorithm 

3. Sollin Algorithm

 

보통 1,2 번이 구현이 쉬워 많이 사용한다. 

위문제는 인접리스트로, 노드의 정보를 생성해 MST 를 구하는 문제이다.

 

---

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

public class Main {
	public static int[] parent;
	public static void make(int v) {
		for(int i  = 1 ; i <= v; i++) {
			parent[i]=i;
		}
	}
	public static int find(int x) {
		if(parent[x]==x) return x;
		else return find(parent[x]);
	}
	public static void union(int a, int b) {
		int pa = find(a);
		int pb = find(b);
		if(pa == pb) return ;
		if(pa > pb ) parent[pb] = pa;
		else parent[pa] = pb;
	}
	public static class node{
		int s , e , w ;

		public node(int s, int e, int w) {
			this.s = s;
			this.e = e;
			this.w = w;
		}
		
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int v =Integer.parseInt(st.nextToken());
		int e =Integer.parseInt(st.nextToken());
		
		parent = new int[v+1]; 
		make(v);
		
		node map[] = new node[e];
		for(int i = 0 ; i < e; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			map[i] = new node(start, end, weight);
		}
		
		Arrays.sort(map , new Comparator<node>() {
			@Override
			public int compare(node o1, node o2) {
				if(o1.w > o2.w) return 1;
				else if( o1.w < o2.w) return -1;
				else return 0;
			}
		});
		
		long answer= 0;
		for( int index=0 ; index < map.length; index++) {
			int pa = find(map[index].s);
			int pb = find(map[index].e);
			if(pa==pb) continue;
			union(pa, pb);
			answer +=map[index].w;
		}
		System.out.println(answer);
	}
}

---