[JAVA] SWEA 1251 하나로 [Kruskal]

전체 코드 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class SWEA_1251_하나로 {

	static int N, T;
	static double E;
	static int arr[], sel[];
	static boolean v[];
	static ArrayList<int[]> arrList;
	static int parent[];
	static PriorityQueue<Vector> pq;

	static class Vector implements Comparable<Vector> { // 시작점과 끝점 그리고 비용을 담는 클래스
		int start, end;
		long weight;

		Vector(int start, int end, long weight) {
			this.start = start;
			this.end = end;
			this.weight = weight;
		}

		@Override
		public int compareTo(Vector o) {
			if (this.weight > o.weight)
				return 1;
			else if (this.weight < o.weight)
				return -1;
			else
				return 0;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		int x[], y[];
		long result, MIN;

		for (int test = 1; test <= T; test++) {

			arrList = new ArrayList<>();

			N = sc.nextInt();

			x = new int[N];
			y = new int[N];
			for (int i = 0; i < N; i++)
				x[i] = sc.nextInt();
			for (int i = 0; i < N; i++)
				y[i] = sc.nextInt();
			E = sc.nextDouble(); // 환경 세율

//			makeCombination();

			print();
			makeSet();

			MIN = Long.MAX_VALUE;

//			for (int[] arr : arrList) {
			pq = new PriorityQueue<Vector>();

			getVectors(x, y); // 모든 연결점에 대해 두 점간의 환경비용을 계산해 연결한다.

			result = 0;
			for (int i = 0; i < N - 1; i++) { // 크루스칼을 통해 최소 비용 트리를 구한다.
				Vector tmp = pq.poll();

				int a = find(tmp.start); // 시작점의 정점을 찾는다
				int b = find(tmp.end); // 끝점의 정점을 찾는다.

				if (a == b) //만약 두 점의 정점이 같다면 다음 루프로
					continue;
				union(a, b); // 그렇지 않다면 두점을 연결한다.
				result += tmp.weight; // 결과 값에 weight을 누적시킨다.
			}

			if (MIN > result)
				MIN = result;
//			}
			System.out.println("#" + test + " " + MIN);

		}

	}

	public static void print() {
		for (int i = 0; i < arrList.size(); i++) {
			System.out.println(Arrays.toString(arrList.get(i)));
		}
	}

	public static void getVectors(int[] x, int[] y) { // 두 점 사이의 비용을 구해 vector ArrayList를 생성
		for (int i = 0; i < N - 1; i++) {
			long weight = (long) (E * (Math.pow((x[i] - x[i + 1]), 2) + Math.pow((y[i] - y[i + 1]), 2)));
			pq.add(new Vector(i, i + 1, weight));
		}
		long weight = (long) (E * (Math.pow((x[0] - x[N - 1]), 2) + Math.pow((y[0] - y[N - 1]), 2)));
		pq.add(new Vector(N - 1, 0, weight));
	}

	public static void makeSet() { // 정점 배열을 생성
		parent = new int[N + 1];
		for (int i = 0; i < N + 1; i++) {
			parent[i] = i;
		}
	}

	public static int find(int a) { // 점에 대해 정점을 찾는 함수
		if (a == parent[a])
			return a;
		parent[a] = find(parent[a]);
		return parent[a];
	}

	public static void union(int a, int b) { // 두점의 정점을 찾아 합치는 함수
		int aRoot = find(a);
		int bRoot = find(b);

		if (aRoot != bRoot) {
			parent[aRoot] = b;
		} else {
			return;
		}
	}
}

 

전형적인 최소비용트리문제이고, 크루스칼을 이용하면 쉽게 풀 수 있었다.

 

각 점들간 환경 비용을 계산하고, 그 점들을 모두 이을 수 있는 최소 비용을 찾는 문제이다.

 

크루스칼에 대해서는 자료가 굉장히 많아 설명을 생략한다.