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

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

1197번: 최소 스패닝 트리

• 풀이

최소 신장 트리는 크루스칼 알고리즘과 프림 알고리즘으로 해결할 수 있다.

나는 그 중 크루스칼 알고리즘을 풀었다.

Edge 클래스를 만들어 각 간선의 정점, 가중치 값을 담고 가중치 오름차순으로 정렬했다.

가중치가 작은 것부터 시작해서 간선이 잇는 두 정점이 같은 그룹이 아니라면 선택하는 방식이다. 두 정점이 이미 같은 그룹이라면 다시 선택했을 때 사이클이 형성되기 때문이다.

두 정점이 같은 그룹인 지 확인하기 위해 부모를 찾는 Find 함수를 사용하였고, 간선이 선택되었을 때 같은 그룹으로 만들어주기 위해 부모를 합치는 Union 함수를 사용하였다.

• 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int V, E;
	static int parent[];
	static Edge edges[];
	static int weight;
	
	static class Edge{
		int u, v, c;
		Edge(int u, int v, int c){
			this.u = u;
			this.v = v;
			this.c = c;
		}
	}
	
	// 같은 그룹인 지 확인
	static int find(int x) {
		if (parent[x] == x) return x;
		return parent[x] = find(parent[x]);
	}
	
	// 같은 그룹으로 합치기
	static void union(int x, int y) {
		x = parent[x];
		y = parent[y];
		
		if (x>y) parent[x] = y;
		else parent[y] = x;
	}
	

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());

		parent = new int[V+1];
		edges = new Edge[E];
		
	  // 부모 배열 초기화
		for (int i=1; i<V+1; i++) parent[i] = i;
		
		// 간선 정보 입력
		for (int i=0; i<E; i++) {
			st = new StringTokenizer(bf.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			edges[i] = new Edge(u, v, c);
		}
		
		// 가중치 오름차순 정렬
		Arrays.sort(edges, (o1, o2) -> (o1.c - o2.c));
		
		// 크루스칼 알고리즘
		for (int i=0; i<E; i++) {
			Edge now = edges[i];
			if (find(now.u) == find(now.v)) continue;
			weight += now.c;
			union (now.u, now.v);
		}

		// 출력
		System.out.println(weight);
	}

}