[SW3124] 최소 스패닝 트리

 SW Expert Academy - 최소 스패닝 트리 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_mSnmKUckDFAWb&categoryId=AV_mSnmKUckDFAWb&categoryType=CODE&problemTitle=%EC%B5%9C%EC%86%8C&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

문제 입출력

1
3 3
1 2 1
2 3 2
1 3 3

#1 3

 

문제 풀이

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


public class Solution {
	static int T, V, E;
	static long ans;
	static int[] p;
	static Edge[] edges;

	static StringBuilder sb = new StringBuilder();


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

		T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());

			// 초기화
			ans = 0;
			p = new int[V + 1];
			edges = new Edge[E];
			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				int w = Integer.parseInt(st.nextToken());

				edges[i] = new Edge(from, to, w);
			}

			makeSet();
			Arrays.sort(edges, (e1, e2) -> e1.w - e2.w);

			int cnt = 0;
			for (Edge e : edges) {
				if (union(e.from, e.to)) {
					ans += e.w;
					if (++cnt == V - 1) break;
				}

			}

			sb.append("#").append(t).append(" ").append(ans).append("\n");

		}

		System.out.println(sb.toString());

	} // end main


	private static void makeSet() {
		for (int i = 0; i <= V; i++) p[i] = i;
	} // end makeSet


	private static int findSet(int a) {
		if (p[a] == a) return a;
		return p[a] = findSet(p[a]);
	} // end findSet


	private static boolean union(int a, int b) {
		int pa = findSet(a);
		int pb = findSet(b);

		if (pa == pb) return false;

		if (pa < pb) p[pb] = pa;
		else p[pa] = pb;

		return true;
	}


	static class Edge {
		int from;
		int to;
		int w;


		public Edge(int from, int to, int w) {
			this.from = from;
			this.to = to;
			this.w = w;
		}


		@Override
		public String toString() {
			return "Edge [from=" + from + ", to=" + to + ", w=" + w + "]";
		}

	}
}

• Kruskal 알고리즘을 이용해서 풀 수 있다.
• weight 을 기준으로 정렬해서 만약 union() 할 수 있다면 union() 을 한다.
• union() 을 하면서 weight 를 더한다.

 

 

 

 

 

 

 

 

 

# SWEA 최소 스패닝 트리

---