최소 스패닝 트리

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

풀이

주의사항
1. 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)이기 때문에 Scanner와 차이가 많이난다.
2. 정점의 갯수가 크기 때문에 배열을 사용한 인접행렬을 사용하면 메모리초과가 난다.
3. 이 경우엔 Kruskal의 성능이 더 좋게 나왔다

소스코드 1. Kruskal 사용

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 Main {
	static int[] parents;
	static int[] rank;

	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());

		int[][] edges = new int[E][3];
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			edges[i][0] = Integer.parseInt(st.nextToken()) - 1;
			edges[i][1] = Integer.parseInt(st.nextToken()) - 1;
			edges[i][2] = Integer.parseInt(st.nextToken());
		}

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

			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return Integer.compare(o1[2], o2[2]);
			}
		});

		parents = new int[V];
		rank = new int[V];

		for (int i = 0; i < V; i++) {
			makeSet(i);
		}

		int sum = 0;
		for (int i = 0; i < E; i++) {
			int px = findSet(edges[i][0]);
			int py = findSet(edges[i][1]);
			int c = edges[i][2];
			if (px != py) {
				sum += c;
				union(px, py);
			}
		}
		System.out.println(sum);
	}

	public static void makeSet(int x) {
		parents[x] = x;
	}

	public static int findSet(int x) {
		if (parents[x] == x)
			return x;
		parents[x] = findSet(parents[x]);
		return parents[x];
	}

	public static void union(int px, int py) {
		if (rank[px] > rank[py])
			parents[py] = px;
		else {
			parents[px] = py;
			if (rank[px] == rank[py])
				rank[py]++;
		}
	}
}

소스코드 2. Prim 우선순위 큐 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static class Node implements Comparable<Node> {
		int d;
		int cost;

		public Node(int d, int cost) {
			this.d = d;
			this.cost = cost;
		}

		@Override
		public int compareTo(Node o) {
			// TODO Auto-generated method stub
			return Integer.compare(this.cost, o.cost);
		}
	}

	static int V, E;

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

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

		List<Node>[] list = new ArrayList[V];
		for (int i = 0; i < V; i++) {
			list[i] = new ArrayList<>();
		}

		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			int cost = Integer.parseInt(st.nextToken());

			list[a].add(new Node(b, cost));
			list[b].add(new Node(a, cost));
		}

		boolean[] visited = new boolean[V];
		PriorityQueue<Node> queue = new PriorityQueue<>();

		visited[0] = true;
		queue.addAll(list[0]);
		int cnt = 0;
		long sum = 0;

		while (!queue.isEmpty()) {
			if (cnt == V)
				break;
			Node node = queue.poll();
			if (visited[node.d])
				continue;

			sum += node.cost;
			queue.addAll(list[node.d]);
			visited[node.d] = true;
			cnt++;
		}
		
		System.out.println(sum);
	}
}