[BOJ] 1197.최소스패닝트리

Kruskal Algorithm

• 메모리 : 50,356 KB

• 실행시간 : 504 ms

• 코드길이 : 1,741 B

• 소요시간 : 1H

package baekjoon;

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_B_1197_최소스패닝트리_Kruskal {

	static int[] parents;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		int[][] edges = new int[E][3];
		parents = new int[V + 1];

		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			edges[i][0] = Integer.parseInt(st.nextToken()); // 정점1
			edges[i][1] = Integer.parseInt(st.nextToken()); // 정점2
			edges[i][2] = Integer.parseInt(st.nextToken()); // 가중치
		}
		// 가중치를 오름차순으로 정렬
		Arrays.sort(edges, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return Integer.compare(o1[2], o2[2]);
			}

		});

		// unionFind를 할 준비 - makeSet과정
		for (int i = 1; i < V + 1; i++) {
			parents[i] = i;
		}

		// V-1번 반복하면서 union진행
		int cnt = 0;
		long result = 0;
		for (int i = 0; i < E; i++) {
			int a = findSet(edges[i][0]);
			int b = findSet(edges[i][1]);

			if (a == b)
				continue;

			union(a, b);
			result += edges[i][2];
			cnt++;
			if (cnt == V - 1)
				break;
		}

		System.out.println(result);
		in.close();
	}

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

	static void union(int a, int b) {
		int px = findSet(a);
		int py = findSet(b);

		parents[py] = px;
	}
}

Prim Algorithm

• 메모리 : 57,220 KB

• 실행시간 : 692 ms

• 코드길이 : 1,888 B

package baekjoon;

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

public class Main_B_1197_최소스패닝트리_Prim {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		long result = 0;

		ArrayList<Edge>[] adj = new ArrayList[V];
		for (int i = 0; i < V; i++) {
			adj[i] = new ArrayList<>();
		}

		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int a = Integer.parseInt(st.nextToken()); // 정점1
			int b = Integer.parseInt(st.nextToken()); // 정점2
			int c = Integer.parseInt(st.nextToken()); // 가중치
			adj[a-1].add(new Edge(b - 1, c));
			adj[b-1].add(new Edge(a - 1, c));
		}

		PriorityQueue<Edge> pq = new PriorityQueue<>();
		Edge[] dist = new Edge[V];
		// dist안의 각 거리들은 무한대
		for (int i = 1; i < V; i++) {
			dist[i] = new Edge(i, Integer.MAX_VALUE);
			pq.add(dist[i]);
		}

		boolean[] mst = new boolean[V + 1];
		// 시작점은 0
		dist[0] = new Edge(0, 0);
		pq.add(dist[0]);
		while (!pq.isEmpty()) {
			// 현재 dist가 가장 작은 친구를 데려와서
			Edge e = pq.poll();
			if (mst[e.dest]) {
				continue;
			}
			mst[e.dest] = true;
			result += e.cost;
			// 그 친구로부터 출발하는 모든 간선에 대해서
			for (Edge next : adj[e.dest]) {
				// 그 간선의 목적지가 아직 pq에 들어있는 정점이라면
				// 그리고 더 빨리 도착할 수 있다면
				if (!mst[next.dest] && dist[next.dest].cost > next.cost) {
					// dist갱신
					dist[next.dest].cost = next.cost;
					// decrease key연산
					pq.remove(dist[next.dest]);
					pq.add(dist[next.dest]);
				}
			}
		}
		System.out.println(result);
		in.close();
	}

	static class Edge implements Comparable<Edge> {
		int dest;
		int cost;

		Edge(int d, int c) {
			dest = d;
			cost = c;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.cost, o.cost);
		}
	}

}