Java : 원더랜드(MST : 크루스칼, 유니온&파인드)

문제

풀이

• 정렬 + 유니온 파인드 문제
• 준비물 :
  • parent : 도시(정점)을 담을 배열
  • Edge : 간선과 비용의 정보를 탐을 클래스
  • union, find : 유니온 파인드 구현체 및 기본 지식
• 회로를 그리되 최소 비용을 구해야 하므로 Edge 클래스 배열을 만든다
• 최소 비용을 구하므로 cost 오름 차순으로 정렬한다.
• Edge 배열의 각 두 정점의 부모가 같은지 확인한다.
• 같다면 연결되어 있는거고 아니면 비용을 추가하고 합쳐준다.
• 끗

잡담

그래프는 회로가 존재하고, 트리는 절대 회로가 존재하지 않는다.
간선의 수 = 정점의 수 - 1

전체 코드

package inflearn;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class I0907 {
	static int[] parent;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int v = sc.nextInt();
		int e = sc.nextInt();
		parent = new int[v + 1];
		ArrayList<Edge> arr = new ArrayList<>();

		// 정점 초기화
		for (int i = 1; i <= v; i++) {
			parent[i] = i;
		}

		// 간선과 비용 초기화
		for (int i = 0; i < e; i++) {
			int v1 = sc.nextInt();
			int v2 = sc.nextInt();
			int cost = sc.nextInt();

			arr.add(new Edge(v1, v2, cost));
		}

		System.out.println(solution(arr));
	}

	static int solution(ArrayList<Edge> arr) {
		int ans = 0;

		// 클래스에서 정의해둔 compareTo 방식으로 정렬한다. cost 오름차순
		Collections.sort(arr);

		// 두 정점의 부모 노드가 다를 때, 즉 서로 연결이 안 되어 있을 때 값을 추가한다.
		for (Edge n : arr) {
			if (find(n.v1) != find(n.v2)) {
				ans += n.cost;
				// 추가했으므로 두 정점은 합쳐준다.
				union(n.v1, n.v2);
			}

		}
		return ans;
	}

	// 파인드 구현체
	static int find(int r) {
		// 부모라면 반환
		if (parent[r] == r) return r;
		// 재귀로 부모를 찾아간다.
		return parent[r] = find(parent[r]);
	}

	// 유니온 구현체
	static void union(int e1, int e2) {
		// e1, e2의 부모 노드를 찾아서 비교한다.
		int a = find(e1);
		int b = find(e2);

		// 부모 노드가 같다면 합쳐진 상태이므로 return
		if (a == b) return;

		// 큰 값이 작은 값 밑으로 들어간다.
		if (a < b) parent[b] = a;
		else parent[a] = b;
	}

	// 간선과 비용 정보를 담을 class
	static class Edge implements Comparable<Edge> {
		int v1, v2, cost;

		public Edge(int v1, int v2, int cost) {
			this.v1 = v1;
			this.v2 = v2;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			return cost - o.cost;
		}
	}
}