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

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

1197번: 최소 스패닝 트리

 

---

저번 여름방학 때 이코테 책으로 배우고 저번학기 자료구조 수업에서도 배웠던 트리.

저번엔 파이썬,C언어로 했지만 이번에는 자바로 작성해서 익숙한듯 익숙하지 않았다

2022.08.08 - [파이썬 공부/이코테] - 8. 기타 그래프 이론: 크루스칼 알고리즘

2022.11.22 - [학교공부/자료구조] - Biconnected Components/최소 비용 신장트리

 

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

public class P1197 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());
		int[] parent = new int[n + 1];
		for (int i = 0; i <= n; i++) {
			parent[i] = i;
		}

		int[][] edges = new int[e][3];
		for (int i = 0; i < e; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			edges[i][0] = c;
			edges[i][1] = v1;
			edges[i][2] = v2;

		}

		Arrays.sort(edges, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] == o2[0])
					return o1[1] - o2[1];
				return o1[0] - o2[0];
			}

		});

		int result = 0;
		for (int i = 0; i < e; i++) {
			int parent_v1 = find(parent, edges[i][1]);
			int parent_v2 = find(parent, edges[i][2]);
			if (parent_v1 == parent_v2) {
				continue;
			} else {
				result += edges[i][0];
				union(parent, edges[i][1], edges[i][2]);
			}
		}

		System.out.println(result);
	}

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

	static void union(int[] parent, int v1, int v2) {
		int parent_v1 = find(parent, v1);
		int parent_v2 = find(parent, v2);
		if (parent_v1 < parent_v2)
			parent[parent_v2] = parent_v1;
		else
			parent[parent_v1] = parent_v2;
	}

}

내용은 이전에 작성했던 코드와 거의 같다.

 

가장 비용이 낮은 간선부터 확인해서, 사이클을 만들지 않는 간선은 추가하고, 아니면 버린다

 

...이 한줄로 설명이 될 것 같다.