[JAVA] 백준 1774번 : 우주신과의 교감

문제

1774번: 우주신과의 교감

해결 방법

크루스칼 알고리즘을 활용해서 풀었다.

크루스칼이란 간단하게만 설명하면, 정점들과 이어진 간선의 거리를 기준으로 정렬한 뒤에 정렬된 순서대로 접근하여

유니온-파인드를 활용하여 앞의 두 정점이 연결되어 있지 않으면 연결시켜주는 방식으로써

가장 짧은 거리의 간선이 제일 앞으로 정렬되어 있기 때문에 제일 짧은 경로를 만들어 낼 수 있다.

 

문제에서 이미 연결된 통로로 주어지는 값들은 거리를 0으로 설정해서 리스트에 입력해주는 방식을 사용하였다.

 

또한 주어진 좌표값에서 거리를 구하는 방식은 피타고라스 정리를 활용하여

(첫번 째 우주신의 x좌표 - 두 번째 우주신의 x좌표)$^2$ + (첫 번째 우주신의 y좌표 - 두 번째 우주신의 y좌표)$^2$

의 결과값의 제곱근이 우주신들 간의 거리가 된다.

 

자바에서는 Math.pow(값, 2) 를 이용하면 주어진 값의 제곱을 double형으로 받을 수 있다.

제곱근 같은 경우는 Math.sqrt(값) 을 통해 주어진 값의 제곱근을 double형으로 받을 수 있다.

이렇게 구한 값들을 uniEdge에 시작지점, 끝지점, 거리 순으로 정리한 뒤에 크루스칼 알고리즘을 활용하면 된다.

 

출력의 조건에서 '소수점 둘째짜리까지' 라고 주어져 있기 때문에

StringFormat을 활용하여 둘째 자리까지 표현했다.

 

코드

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


public class Main {
	static int parent[];
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		parent = new int[N + 1];
		ArrayList<uniGod> godList = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			godList.add(new uniGod(x, y)); // 주어진 x, y값을 저장해둠
			parent[i + 1] = i + 1;
		}
		
		ArrayList<uniEdge> edgeList = new ArrayList<>();
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			edgeList.add(new uniEdge(x, y, 0)); // 이미 연결되어 있는 길은 거리 0으로 저장
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				double xPow = Math.pow(godList.get(i).x - godList.get(j).x, 2);
				double yPow = Math.pow(godList.get(i).y - godList.get(j).y, 2);
				double dist = Math.sqrt(xPow + yPow); // 피타고라스 정리로 거리를 구함
				
				edgeList.add(new uniEdge(i + 1, j + 1, dist)); // 시작점과 끝점이 1부터 시작하기 때문에 1씩 더해줌
			}
		} 
		
		// 여기서 부터 크루스칼 알고리즘 활용
		Collections.sort(edgeList);
		
		double result = 0;
		for (int i = 0; i < edgeList.size(); i++) {
			if (find(edgeList.get(i).start) != find(edgeList.get(i).end)) {
				union(edgeList.get(i).start, edgeList.get(i).end);
				result += edgeList.get(i).distance;
			}
		}
		
		System.out.println(String.format("%.2f", result));
	
	}
	
	static int find(int a) {
		if (parent[a] == a) return a;
		
		return parent[a] = find(parent[a]);
	}
	
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		
		if (a != b) {
			parent[b] = a;
		}
	}
}

class uniGod {
	int x;
	int y;
	
	uniGod(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

class uniEdge implements Comparable<uniEdge> {
	int start;
	int end;
	double distance;
	
	uniEdge (int start, int end, double distance) {
		this.start = start;
		this.end = end;
		this.distance = distance;
	}

	@Override
	public int compareTo(uniEdge o) {
		// TODO Auto-generated method stub
		if (distance < o.distance) return -1;
		
		return 1;
	}
}