7 min to read

java-크루스칼알고리즘-SWEA-하나로-1251

SWEA-크루스칼-알고리즘-최소비용

Featured image

오랜만에 SWEA문제

알고리즘 담당 강사님께서 SWEA의 하나로 문제를 꼭 풀어보시기 바란다고 이야기하셔서

주말을 이용하여 문제를 풀어봤습니다.

최소비용을 탐색하는 알고리즘으로 섬들을 잇는 다리나 비용이 존재하는게 아니고

각 섬들의 정점만 주어지기 때문에 정점이 주어졌을때 거리를 구하는 공식을 사용하고

섬들이 모두 이어져 있는지 없는지 FindSet과 UnionSet을 사용해서 문제를 풀었습니다.

SWEA 하나로

문제출처 - https://swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AV15StKqAQkCFAYD

문제

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

문제 설명

문제는 간단하게 각 섬들의 정점이 주어집니다. 세율이라는 그 섬들을 이어주는 거리비용이 존재하고 가장 최소 비용으로 모든 섬들을 연결하면 되는 문제입니다.

[입력]

가장 첫 줄은 전체 테스트 케이스의 수이다.

각 테스트 케이스의 첫 줄에는 섬의 개수 N이 주어지고 (1≤N≤1,000),

두 번째 줄에는 각 섬들의 정수인 X좌표, 세 번째 줄에는 각 섬들의 정수인 Y좌표가 주어진다 (0≤X≤1,000,000, 0≤Y≤1,000,000).

마지막으로, 해저터널 건설의 환경 부담 세율 실수 E가 주어진다 (0≤E≤1).

[출력]

각 테스트 케이스의 답을 순서대로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다. 이때 C는 케이스의 번호이다.

같은 줄에 빈칸을 하나 두고, 주어진 입력에서 모든 섬들을 잇는 최소 환경 부담금을 소수 첫째 자리에서 반올림하여 정수 형태로 출력하라.

package swea;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 하나로 {
	static double result;
	static int root[];
	static int map[][];
	static ArrayList<island> arr;
	static long [] visitIsland;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//0 0
		//0 100 길이L 제곱 * E
		//우선순위큐 가중치 기준 정점 계산
		//소수 첫쨰 자리에서 반올림후 정수로 계산
		int testcase = Integer.parseInt(br.readLine());
		for(int t = 0 ; t < testcase; t++) {
			//N 섬의갯수 천개들어오면 각자 1번섬 2번섬 3번섬 4번섬 => 7번
			//x좌표 
			//y좌표
			//세율 E
			int N = Integer.parseInt(br.readLine());
			PriorityQueue<Node> pq =  new PriorityQueue<Node>(new Comparator<Node>() {
				@Override
				public int compare(Node o1, Node o2) {
					if(o1.weight<o2.weight) {
						return -1;
					}else {
						return 1;
					}
				}
			});
			arr = new ArrayList<>();
			//X좌표
			StringTokenizer stX = new StringTokenizer(br.readLine());
			//Y좌표
			StringTokenizer stY = new StringTokenizer(br.readLine());
			for(int i = 0 ; i<N; i++) {
				double x = Double.parseDouble(stX.nextToken());
				double y = Double.parseDouble(stY.nextToken());
//				map[x][y] = 1;
				arr.add(new island(x,y));
			}
			double E = Double.parseDouble(br.readLine());
			for(int i=0; i<N; i++) {
				island node = arr.get(i);
				for(int j = i+1; j<N;j++) {
					island node2 = arr.get(j);
					double X = (node.x-node2.x)*(node.x-node2.x);
					double Y = (node.y-node2.y)*(node.y-node2.y);
					pq.add(new Node(i,j,X+Y));
				}
			}
			root = new int[N];
			for(int i=0;i<N;i++) {
				root[i]=i;
			}
			double result = 0;
			while(!pq.isEmpty()) {
				Node node = pq.poll();
				int start = find(node.start);
				int end = find(node.end);
				if(start==end) {
					continue;
				}
				union(start,end);
				double weight = node.weight;
				result += (weight*E);
			}
			System.out.println("#"+(t+1)+" "+Math.round(result));
		}
	}
	private static void union(int start, int end) {
		if(start<end) {
			root[end] = root[start];
		}else {
			root[start]=root[end];
		}
	}
	private static int find(int start) {
		if(root[start]!=start) {
			return find(root[start]);
		}
		return start;
	}
	static class island{
		double x;
		double y;
		island(double x, double y){
			this.x=x;
			this.y=y;
		}
	}
	static class Node{
		int start;	//시작섬
		int end;	//도착섬
		double weight;
		Node(int start, int end, double weight){
			this.start=start;
			this.end=end;
			this.weight=weight;
		}
		
	}

}

모든 섬들을 연결하기 위해서 각자 자신의 섬 번호를 붙인뒤

			root = new int[N];
			for(int i=0;i<N;i++) {
				root[i]=i;
			}

이동을 할때마다 모든 섬들이 이미 연결이 되어있는지

연결이 필요한지 findSet과 UnionSet을 이용해서 확인합니다.

아래의 두 함수가 간단하게 findSet과 UnionSet을 구현한것입니다.

	private static void union(int start, int end) {
		if(start<end) {
			root[end] = root[start];
		}else {
			root[start]=root[end];
		}
	}
	private static int find(int start) {
		if(root[start]!=start) {
			return find(root[start]);
		}
		return start;
	}