[SWEA][Java][D4][최소 신장 트리,크루스칼] 1251 - 하나로

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD

SW Expert Academy

---

문제 풀이

 

이 문제는 전형적인 최소 신장 트리 문제이다.

 

최소 신장 트리 문제를 해결하는 방법은 크루스칼, 프롬 알고리즘이 있다.

 

해당 문제는 크루스칼로 접근해서 풀었고 크루스칼로 풀기 위해서는 Union 파인드를 알아야 한다.

 

유니온 파인드란 해당 부모를 찾아 부모가 같은지 확인하는 것이고 이는 그래프가 순환되는 트리로 연결되는지 확인할 때 사용된다.

 

크루스칼은 가중치가 낮은 순으로 연결하면서 순환 트리로 연결되면 생략하고 연결되지 않으면 연결하는 식으로 풀어나간다. 

 

코드는 다음과 같다.

package com.ssafy.graph;

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

/**
 * 1251. [S/W 문제해결 응용] 4일차 - 하나로 D4 최소 스패닝 => 크루스칼 or 프
 */
public class SWEA_D4_1251_하나로 {

	static class Edge implements Comparable<Edge> {
		int from, to;
		long weight;

		public Edge(int from, int to, long weight) {
			super();
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

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

	static int N;
	static double E;
	static int parents[];
	static Edge[] edgeList;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			N = Integer.parseInt(br.readLine());
			
			int[][] arr = new int[N][2];
			// 섬 정보 저장
			st = new StringTokenizer(br.readLine(), " ");
			for(int i=0;i<N;i++) arr[i][0]=Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine(), " ");
			for(int i=0;i<N;i++) arr[i][1]=Integer.parseInt(st.nextToken());
			
			E = Double.parseDouble(br.readLine());
			
			edgeList = new Edge[N*(N-1)/2];
			// 간선 정보 계산
			int edgeCnt=0;
			for (int i = 0; i < N; i++) {
				for (int j = i + 1; j < N; j++) {
					edgeList[edgeCnt++]=new Edge(i,j,(long)(Math.pow(arr[i][0]-arr[j][0],  2) + Math.pow(arr[i][1]-arr[j][1], 2)));
				}
			}
			// 크루스칼을 위한 가중치 정렬
			Arrays.sort(edgeList);
			
			parents = new int[N];
			make();
			long result=0;
			int count=0;
			
			for(Edge edge: edgeList) {
				if(union(edge.from,edge.to)) {
					result+=edge.weight;
					if(++count==N-1) break;
				}
			}
			System.out.printf("#%d %d\n",tc,Math.round(E*result));
			
		}	
	}
	
	static void make() {
		for (int i = 0; i < N; i++) {
			parents[i]=i;
		}
	}
	
	// 대표자 찾기 
	static int findSet(int a) {
		if(parents[a]==a) return a;
		
		return parents[a]=findSet(parents[a]);
	}
	
	static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		
		if(aRoot==bRoot) return false;
		
		parents[bRoot]=aRoot;
		return true;
	}
	
}