[Java] SWEA 1251번 하나로

SW Expert Academy

---

풀이

Kruskal 알고리즘을 적용하기 위해 우선 만들 수 있는 간선을 전부 만들며 간선 리스트를 만들었습니다.

이때, 문제에서 주어진 조건에 맞추어 가중치를 미리 처리하고 저장을 해야 Kruskal 알고리즘을 사용할 때 정확한 결과가 나올 수 있습니다.

그다음 만든 간선 리스트 edgeList와 Kruskal 알고리즘을 사용해서 MST를 만들어 최소의 환경부담금을 지불할 수 있도록 하여 해결했습니다.

---

코드

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

public class Solution {
	public static class Edge implements Comparable<Edge> {
		int from, to;
		double weight;

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

		@Override
		public int compareTo(Edge o) {
			return Double.compare(this.weight, o.weight);
		}
	}
	
	public static int N;
	public static double E, answer;
	public static int[] x, y;
	public static int[] parents, rank;
	public static Edge[] edgeList;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder("");
		StringTokenizer st = null;		
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; ++tc) {
			N = Integer.parseInt(br.readLine());
			
			parents = new int[N];
			rank = new int[N];
			x = new int[N];
			y = new int[N];
			
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < N; ++i) {
				x[i] = Integer.parseInt(st.nextToken());
			}
			
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < N; ++i) {
				y[i] = Integer.parseInt(st.nextToken());
			}
			
			E = Double.parseDouble(br.readLine());
			
			// 간선리스트를 만든다.
			int e = (N * (N - 1)) / 2;
			int v = 0;
			edgeList = new Edge[e];
		
			for (int i = 0; i < N; ++i) {
				int x1 = x[i];
				int y1 = y[i];
				
				for (int j = i + 1; j < N; ++j) {
					int x2 = x[j];
					int y2 = y[j];
					
					// ?
					double weight = Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2);
					edgeList[v++] = new Edge(i, j, weight * E);
				}
			}
			
			Arrays.sort(edgeList);
			
			make();
			answer = 0;
			
			for (Edge edge : edgeList) {
				if (union(edge.from, edge.to)) {
					answer += edge.weight;
				}
			}
			
			sb.append("#").append(tc).append(" ").append(Math.round(answer)).append("\n");
		}
		
		System.out.println(sb);
	}
	
	public static void make() {
		for (int i = 0; i < N; ++i) {
			parents[i] = i;
		}
	}
	
	public static int find(int a) {
		if (a == parents[a]) {
			return a;
		}
		
		return parents[a] = find(parents[a]);
	}
	
	public static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		
		if (aRoot == bRoot) {
			return false;
		}
		
		if (rank[aRoot] < rank[bRoot]) {
			parents[aRoot] = bRoot;
		}
		else {
			parents[bRoot] = aRoot;
			
			if (rank[aRoot] == rank[bRoot]) {
				rank[aRoot]++;
			}
		}
		
		return true;
	}
}

---

pyo7410/Algorithm