[SWEA][JAVA] 3124 - 최소 스패닝 트리

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_mSnmKUckDFAWb&categoryId=AV_mSnmKUckDFAWb&categoryType=CODE&problemTitle=3124&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

 

문제

 

 

설명

문제에서 나와 있듯이, Prim 또는 Kruscal 알고리즘을 그대로 구현해 보는 문제입니다.

저는 간선 리스트와 서로소 집합을 활용하는 크루스칼 알고리즘을 구현했는데, 과정은 다음과 같습니다.

 

1. 간선을 가중치를 기준으로 오름차순 정렬

2. 크기가 작은 순서대로, 서로소 집합의 union을 통해 사이클이 생기지 않게 간선을 선택해 나가기

3. 선택한 간선이 V-1개가 되면 종료

 

 

 

코드

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

public class SWEA3124_SpanningTree {
	
	static class Node{
		int start, end, weight;
		public Node(int start, int end, int weight) {
			super();
			this.start = start;
			this.end = end;
			this.weight = weight;
		}
	}
	
	static int[] parent;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine()); //전체 테케 수
		
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int V = Integer.parseInt(st.nextToken()); //정점의 갯수
			int E = Integer.parseInt(st.nextToken()); //간선의 갯수
			
			Node[] edgeList = new Node[E];
			parent = new int[V+1]; //정점 번호가 1부터 시작
			
			for(int i=0; i<E; i++) {
				st = new StringTokenizer(br.readLine());
				int start = Integer.parseInt(st.nextToken());
				int end = Integer.parseInt(st.nextToken());
				int weight = Integer.parseInt(st.nextToken());
				edgeList[i] = new Node(start, end, weight);
			}
			
			Arrays.sort(edgeList, new Comparator<Node>() { //가중치를 기준으로 정렬

				@Override
				public int compare(Node o1, Node o2) {
					return o1.weight - o2.weight;
				}
			});
			
			make(); //각 vertex를 단위 집합으로 만듦
			
			int cnt=0; //선택한 간선의 갯수
			long result=0; //최소신장트리 비용
			
			for(int i=0; i<E; i++) {
				Node edge = edgeList[i];
				if(union(edge.start, edge.end)) { //간선 선택 가능하면
					cnt++;
					result+=edge.weight;
					if(cnt==V-1) { //spanning tree 다 완성됐다면
						break;
					}
				}
			}
			System.out.println("#" + tc + " " + result);
		}
	}

	private static void make() { //서로소 단위집합 만들기
		for(int i=1; i<parent.length; i++) {
			parent[i]=i;
		}
	}
	
	private static int find(int a) {
		
		if(parent[a]==a)
			return a;
		
		return parent[a] = find(parent[a]);
	}
	
	private static boolean union(int a, int b){
		int aRoot = find(a);
		int bRoot = find(b);
		
		if(aRoot==bRoot)
			return false;
		
		parent[bRoot] = aRoot;
		return true;
	}
}