[백준] 1197 최소 스패닝 트리

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

2020-11-07

---

# 스패닝 트리 (Spanning Tree) 란 모든 정점들을 최소 간선의 수로 연결한 트리. 

  - 모든 정점이 연결이 되어 있어야 함

  - 사이클을 포함해서는 안됨

  - n개의 정점을 n-1개의 간선으로 연결

 

#최소 스패닝 트리(Minimum Spanning Tree) 란 Spanning Tree에서 정점들을 연결한 간선들의 가중치 합이 최소인 트리.

  1) 크루스칼 (Kruskal) 알고리즘

     - 가중치가 가장 낮은 간선을 선택하고 정점들을 이어나감

     - 이 때, 사이클의 생성을 막기 위해 union-find를 사용함

  2) 프림(Prim) 알고리즘

     - 정점을 기준으로 함

 

 

// 최소 스패닝 트리
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

class Graph implements Comparable<Graph> {
	int start;
	int end;
	int weight;

	Graph(int start, int end, int weight) {
		this.start = start;
		this.end = end;
		this.weight = weight;
	}

	@Override
	public int compareTo(Graph o) {
		return this.weight - o.weight;
	}
}

public class Main1197 {
	public static int V, E, parent[], result;
	public static List<Graph> list;

	public static void union(int x, int y) {
		x = find(x);
		y = find(y);

		if (x != y) {
			parent[y] = x;
		}
	}

	public static int find(int x) {
		if(parent[x] == x) return x;
		return parent[x] = find(parent[x]);
	}

	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		list = new ArrayList<Graph>();
		parent = new int[V+1];
		result = 0;
		for(int i = 1; i <= V; i++) parent[i] = i;
		
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(bf.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			list.add(new Graph(start, end, weight));
		}

		Collections.sort(list);

		for(int i = 0; i < list.size(); i++) {
			int start = list.get(i).start;
			int end = list.get(i).end;
			if(find(start) != find(end)) {
				union(start, end);
				result += list.get(i).weight;
			}
		}
		
		System.out.println(result);
	}
}

 

크루스칼 알고리즘으로 풀었다.

 

1. parent 객체를 초기화 한다.

 

2. 가중치를 기준으로 오름차순 정렬을 한다.

 

3. 정렬한 가중치를 기준으로, 가중치가 작은 간선부터 체크한다.

 3-1) union-find를 이용하여 정점이 연결되어 있다면, union을 해주고 가중치를 더해준다.

 3-2) 이미 연결되어 있다면, 가중치를 더하지 않는다.

 

	@Override
	public int compareTo(Graph o) {
		return this.weight - o.weight;
	}

처음 제출 했을 때 compareTo 메서드에서 작을 때, 같을 때, 클 때 3가지 케이스를 모두 커버 못해서 틀렸었다.