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

접근법

가장 기본적인 최소 신장 트리

간선의 정보를 가중치 기준 오름차순 정렬한 뒤 사이클이 돌지 않는 선에서 선들을 이어준다.

• 추가
• V-1만큼을 이어주면 탈출하는 조건을 넣는다면 좀 더 시간이 빨라질 것 같다. ⇒ 미묘한 성능 향상

---

코드

package boj;

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 BOJ_1197_최소_스패닝_트리 {
	static int[] parent;
	static int sum = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());

		parent = new int[V + 1];
		for (int i = 1; i <= V; i++) {
			parent[i] = i;
		}
		ArrayList<int[]> v = new ArrayList<>();

		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());
			v.add(new int[] { A, B, C });

		}

		Collections.sort(v, (o1, o2) -> o1[2] - o2[2]);

		for (int i = 0; i < E; i++) {
			int[] tmp = v.get(i);
			if (find_root(tmp[0]) == find_root(tmp[1])) {
				continue;
			} else {
				merge(tmp[0], tmp[1]);
				sum += tmp[2];
			}

		}
		System.out.println(sum);

	}

	static int find_root(int node) {
		if (node == parent[node])
			return node;

		return parent[node] = find_root(parent[node]);
	}

	static void merge(int n1, int n2) {
		parent[find_root(n1)] = find_root(n2);
	}

}

결과

메모리	시간	언어
50408KB	648ms	Java