[devmoon] 백준 1197 - (Java)최소 스패닝 트리

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

1197번: 최소 스패닝 트리

1. 유형

프림, 크루스칼, union-find

 

2. 시뮬레이션

 

1. 크루스칼 알고리즘

uion-find를 활용한다.

두 노드의 부모가 일치하면 연결됐다는 의미

다르다면 연결이 안 됐다는 의미

 

3. 코드

1. 크루스칼

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

public class Main {
	static class Node implements Comparable<Node> {
		int from, to, weight;

		Node(int from, int to, int weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		public int compareTo(Node o) {
			return this.weight - o.weight;
		}
	}

	static int N, E, answer;
	static Node edges[];
	static int parent[];

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		E = stoi(st.nextToken());
		edges = new Node[E];
		parent = new int[N + 1];
		answer = 0;
		for (int i = 1; i <= N; i++) {
			parent[i] = i;
		}
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(in.readLine());
			int a = stoi(st.nextToken());
			int b = stoi(st.nextToken());
			int c = stoi(st.nextToken());
			edges[i] = new Node(a, b, c);
		}
		Arrays.sort(edges);
		for (Node edge : edges) {
			if(find(edge.from) == find(edge.to)) continue;
			answer += edge.weight;
			union(edge.from, edge.to);
		}
		System.out.println(answer);
	}
	static void union(int c1, int c2) {
		c1 = find(c1);
		c2 = find(c2);
		if(c1< c2)
			parent[c2] = c1;
		else
			parent[c1] = c2;
	}
	static int find(int child) {
		if(parent[child] == child)
			return child;
		return parent[child] = find(parent[child]);
	}
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}