[BaekJoon] 1197 최소 스패닝 트리 (Java)

1.  문제 링크

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

2.  문제

요약

• 최소 스패닝 트리는 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말합니다.
• 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 10,000보다 작거나 같은 정점의 개수 V와 1보다 크거나 같고 100,000보다 작거나 같은 간선의 개수 E가 주어지고 두 번째 줄부터 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어집니다. 이는 A번 정점과 B번 정점이 절댓값이 1,000,000을 넘지 않는 가중치 C인 간선으로 연결되어 있다는 의미입니다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어집니다.
  • 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있습니다.
• 출력: 첫 번째 줄에 최소 스패닝 트리의 가중치를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	static int V, E, totalWeight;
	static int[] parents, rank;
	static ArrayList<Edge> edges;
	static void input() {
		Reader scanner = new Reader();
		edges = new ArrayList<>();
		V = scanner.nextInt();
		E = scanner.nextInt();
		totalWeight = 0;
		parents = new int[V + 1];
		rank = new int[V + 1];
		for(int i = 1; i <= V; i++) {
			parents[i] = i;
		}
		for(int i = 0; i < E; i++) edges.add(new Edge(scanner.nextInt(), scanner.nextInt(), scanner.nextInt()));
	}
	
	static void kruskal() {
		ArrayList<Edge> mst = new ArrayList<>();
		Collections.sort(edges);
		for(Edge edge : edges) {
			if(mst.size() == V - 1)
				break;
			if(!isSameParents(edge.s_node, edge.e_node)) {
				union(edge.s_node, edge.e_node);
				mst.add(edge);
			}
		}
		for(Edge e : mst) {
			totalWeight += e.weight;
		}
		System.out.println(totalWeight);
	}
	
	static int findParents(int node) {
		if(parents[node] == node) return node;
		return parents[node] = findParents(parents[node]);
	}
	
	static void union(int s_node, int e_node) {
		int s_parent = findParents(s_node);
		int e_parent = findParents(e_node);
		if(s_parent != e_parent) {
			if(s_parent < e_parent) parents[e_parent] = s_parent;
			else parents[s_parent] = e_parent;
		}
	}
	
	static boolean isSameParents(int s_node, int e_node) {
		int s_parent = findParents(s_node);
		int e_parent = findParents(e_node);
		if(s_parent == e_parent) return true;
		return false;
	}
	
	public static void main(String[] args) {
		input();
		kruskal();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
	
	static class Edge implements Comparable<Edge> {
		int s_node, e_node, weight;
		public Edge(int s_node, int e_node, int weight) {
			this.s_node = s_node;
			this.e_node = e_node;
			this.weight = weight;
		}
		@Override
		public int compareTo(Edge e) {
			// TODO Auto-generated method stub
			return this.weight - e.weight;
		}
	}
}

4.  접근

신장 트리(Spanning Tree)

• 그래프에서 모든 정점을 포함하고, 정점 간에 서로 연결이 되며 사이클이 존재하지 않는 그래프를 뜻합니다.
• 따라서 신장 트리는 정점의 개수가 V개일 때, 간선은 (V - 1)개가 됩니다.
• 한 그래프에서 여러 신장 트리가 나올 수 있습니다.
• 최소 신장 트리(MST(Minimum Spanning Tree))는 그러한 여러 신장 트리 중에서 가중치의 합이 최소가 되는 신장 트리를 뜻합니다.
• 최소 신장 트리(MST)를 구할 때는 Kruskal(크루스칼) 알고리즘을 이용하여 구할 수 있습니다.

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

• 크루스칼 알고리즘은 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용되는 알고리즘입니다.
• 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결선을 그었을 때 가중치의 합이 최소가 되는 상황을 구할 때 사용합니다.
• 최소 신장 트리(MST)를 구할 때 해당 알고리즘을 사용합니다.
• 그래프 간선들을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않게 정렬된 순서대로 간선을 선택하며 해당 알고리즘을 진행합니다.

1. 그래프 간선들을 가중치의 오름차순으로 정렬합니다.
   

2. C - E부터 선택합니다.
   

3. A - D를 선택합니다.
   

4. B - E를 선택합니다.
   

5. B - C를 선택합니다. 그러나 B - C - E로 사이클이 생기기 때문에 이는 선택하지 않습니다.
   

6. A - C를 선택합니다. 선택된 간선의 개수가 정점 개수 - 1 개이므로 종료합니다.
   

• 사이클을 판단할 때는 Union Find 알고리즘을 이용하여 판단합니다.
• Union-Find 알고리즘 문제는 아래 링크를 통해 확인할 수 있습니다.

  Union-Find 알고리즘