[SWEA] - 최소 스패닝 트리 / 3124번 (Java)

[SWEA] - 최소 스패닝 트리 / 3124번 (Java)

[SWEA] - 최소 스패닝 트리 / 3124번 (Java)

1. 문제 접근

MST의 가장 기본적인 예제로 크루스칼 알고리즘과 Union-Find알고리즘을 통해 구현하였다.

 

크루스칼 알고리즘을 이용한 MST의 흐름은 다음과 같다.

1. 무향 가준치 그래프에서 주어진 간선의 정보를 저장한다.
2. 간선의 정보를 가중치를 기준으로 오름차순으로 정렬한다.
3. 간선의 가중치가 작은 순서대로 트리를 완성시킨다.
   • 이 때, 사이클이 발생한다면 해당 간선은 추가하지 않는다.
4. 간선의 개수가 V-1개(V: 정점의 개수)가 되면 반복을 중단한다.

 

---

2. 코드

package swea;

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

/**
 * [SWEA] - 최소 스패닝 트리 / 3124번 
 * @author JinHxxxxKim
 * 
 * 1. test case의 수 T(1≤T≤10)를 입력받는다.
 * 2. 정점의 개수 V(1≤V≤100,000)와 간선의 개수 E(1≤E≤200,000)를 입력받는다.
 * 3. 각 간선에 대한 정보를 나타내는 세 정수 A, B, C를 입력받아 간선의 정보를 저장한다.
 * 		- 이때 가중치의 최대값은 1,000,000, MST 간선의 개수는 100,000 따라서 가중치의 합은 long형으로 선언
 * 4. 간선의 정보를 가중치를 기준으로 오름차순으로 정렬한다.
 * 5. makeSet() 호출
 * 6. 간선의 개수가 V-1이 될때까지 반복
 * 		- 간선을 하나 뽑는다.
 * 		- to, from이 서로소 집합이라면 union한 뒤, 가중치를 더한다.
 * 7. 가중치 출력
 */
public class Sol_3124 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;

	// 그래프 정보
	private static int V, E;
	private static Edge[] edgeList;

	// UnionFind 정보
	private static int[] parents;

	public static void main(String[] args) throws Exception {
		int TC = Integer.parseInt(br.readLine().trim());
		for (int testCase = 1; testCase <= TC; testCase++) {
			st = new StringTokenizer(br.readLine().trim());
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			edgeList = new Edge[E];

			for (int edgeCnt = 0; edgeCnt < E; ++edgeCnt) {
				st = new StringTokenizer(br.readLine().trim());
				int node1 = Integer.parseInt(st.nextToken()) - 1;
				int node2 = Integer.parseInt(st.nextToken()) - 1;
				int weight = Integer.parseInt(st.nextToken());
				edgeList[edgeCnt] = new Edge(node1, node2, weight);
			}
			// 간선 정렬
			Arrays.sort(edgeList);
			// makeSet()호출
			makeSet();
			int weightSum = 0;
			int edgeCnt = 0;
			for (Edge currEdge : edgeList) {
				// 서로 다른 집합에 속할 경우
				if (union(currEdge.node1, currEdge.node2)) {
					weightSum += currEdge.weight;
					++edgeCnt;
				}
				if (edgeCnt == V - 1)
					break;
			}

			sb.append(String.format("#%d %d\n", testCase, weightSum));
		}
		System.out.println(sb);
	}

	// 매개변수로 전달된 node1, node2의 집합을 합치는 메소드
	private static boolean union(int node1, int node2) {
		int aRoot = find(node1);
		int bRoot = find(node2);
		// 이미 같은 집합에 속한다
		if (aRoot == bRoot)
			return false;
		parents[aRoot] = bRoot;
		return true;
	}

	// 매개변수로 전달됭 node의 루트를 찾는 메소드
	private static int find(int node) {
		if (parents[node] == node)
			return node;
		else
			return parents[node] = find(parents[node]);
	}

	// unionFind 전처리
	private static void makeSet() {
		parents = new int[V];
		for (int node = 0; node < V; ++node) {
			parents[node] = node;
		}

	}

	// 간선 클래스
	static class Edge implements Comparable<Edge> {
		int node1, node2;
		int weight;

		public Edge(int node1, int node2, int weight) {
			super();
			this.node1 = node1;
			this.node2 = node2;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge edge) {
			return Long.compare(this.weight, edge.weight);
		}

	}
}

 

---

3. 디버깅

간단한 MST 문제지만 한가지 고려해야할 사항이 있다.

 

입력값을 보면 "정점의 개수 V(1≤V≤100,000), 가중치는 절대값이 1,000,000을 넘지 않는다." 라고 명시되어있다.

 

모든 간선의 가중치가 1,000,000이고, 정점의 개수가 100,000일 경우 가중치의 합은 대략 100,000,000,000으로 1000억까지 커질 수 있다. 

 

따라서 가중치의 합을 저장하는 변수의 자료형은 `int`로는 부족하며 `long`이 되어야 오버플로우가 발생하지 않는다.

 

---

4. 결과