아이디어

• ㅈㄱㄴ
• E가 V에 비해 크지 않으므로 Kruskal로 ㄱ
• make랑 union은 굳이 메소드 안 만들었습니다.
• 나름 최적화한답시고 경로압축이랑 큰 번호쪽이 루트가 되도록?

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;
	
	static int V, E;
	static long ans;
	static Edge[] edgeList;
	static int[] parents;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		V = Integer.parseInt(tk.nextToken());
		E = Integer.parseInt(tk.nextToken());

		edgeList = new Edge[E];
		parents = new int[V+1];		// 1-base
		
		for (int i=0; i<E; i++) {
			tk = new StringTokenizer(rd.readLine());
			int A = Integer.parseInt(tk.nextToken());
			int B = Integer.parseInt(tk.nextToken());
			int C = Integer.parseInt(tk.nextToken());
			edgeList[i] = new Edge(A, B, C);
		}
		
		Arrays.sort(edgeList);
		
		// make
		for (int i=1; i<=V; i++) {
			parents[i] = i;
		}
		
		// union
		int cnt = 0;
		for (int i=0; ; i++) {
			Edge e = edgeList[i];
			int pv1 = find(e.v1);
			int pv2 = find(e.v2);
			if (pv1 == pv2) continue;
			if (pv1 < pv2) parents[pv1] = pv2;
			else parents[pv2] = pv1;
			ans += e.w;
			cnt++;			
			if (cnt == V - 1) break;
		}
		
		System.out.println(ans);
	}
	
	static class Edge implements Comparable<Edge>{
		int v1, v2;
		long w;
		public Edge(int v1, int v2, long w) {
			super();
			this.v1 = v1;
			this.v2 = v2;
			this.w = w;
		}
		@Override
		public int compareTo(Edge o) {
			return Long.compare(this.w, o.w);
		}
	}
	
	static int find(int x) {
		if (parents[x] == x) return x;
		else return parents[x] = find(parents[x]);
	}
}

메모리 및 시간

• 메모리: 49608 KB
• 시간: 628 ms

리뷰

• 기본기는 확실히