아이디어

• 모든 컴퓨터를 연결하는 데 최소 비용이 들도록 한다. → 최소 스패닝 트리 문제
  • Prim 알고리즘의 시간복잡도는 $O(V^2)$ 또는 $O((V+E)\lg V)$로, 우선순위 큐를 사용하면 풀이가 가능하다.
  • Kruskal 알고리즘의 시간복잡도는 $O(E \lg E)$로, 풀이가 가능하다.
• 정점 수 N에 비해 간선 수 M이 크지 않으므로 Kruskal 알고리즘을 사용해 풀이했다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;

	static int N, M, ans;
	static List<Edge> edgeList = new ArrayList<>();
	static int[] parents;
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(rd.readLine());
		M = Integer.parseInt(rd.readLine());
		
		for (int i=0; i<M; i++) {
			tk = new StringTokenizer(rd.readLine());
			int a = Integer.parseInt(tk.nextToken());
			int b = Integer.parseInt(tk.nextToken());
			int w = Integer.parseInt(tk.nextToken());
			edgeList.add(new Edge(a, b, w));
		}
		
		// make-set
		parents = new int[N+1];
		for (int i=1; i<=N; i++) {
			parents[i] = i;
		}
		
		// kruskal
		edgeList.sort((e1, e2) -> Integer.compare(e1.w, e2.w));
		
		int cnt = 0;
		int idx = 0;
		while (cnt < N - 1) {
			Edge e = edgeList.get(idx++);
			if (union(e.v1, e.v2)) {
				ans += e.w;
				cnt++;
			}
		}
		
		System.out.println(ans);
	}
	
	static class Edge {
		int v1, v2, w;
		Edge(int v1, int v2, int w) {
			this.v1 = v1;
			this.v2 = v2;
			this.w = w;
		}
	}
	
	static int findSet(int x) {
		if (parents[x] == x) return x;
		return parents[x] = findSet(parents[x]);
	}
	
	static boolean union(int x, int y) {
		int px = findSet(x);
		int py = findSet(y);
		if (px == py) return false;
		parents[py] = px;
		return true;
	}
}

메모리 및 시간

• 메모리: 49544 KB
• 시간: 584 ms

리뷰

• 단순 MST 문제