BOJ - 4386 별자리 만들기

BOJ - 4386 별자리 만들기

(문제 : https://www.acmicpc.net/problem/4386)

문제 해결 방법

조건을 보고 크루스칼 알고리즘을 채택함.
1. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
2. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
위의 조건은 최소 스패닝 트리를 만족함. 다만 입력값으로 edge들을 주는 것이 아님. 따라서 각각의 노드 별 거리값을 구하여 edge를 구한 다음 크루스칼 알고리즘을 사용하면 문제를 해결할 수 있음.

해결 및 최종 코드

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

public class Main {
	public static int stoi(String s) {return Integer.parseInt(s);}
	public static double stod(String s) {return Double.parseDouble(s);}
	public static class Edge implements Comparable<Edge> {
		int start, end;
		double w;
		
		Edge(int s, int e, double w) {
			this.start = s;
			this.end = e;
			this.w = w;
		}
		
		@Override
		public int compareTo(Edge o) {
			if(this.w - o.w > 0) return 1;
			else if(this.w - o.w == 0) return 0;
			else return -1;
		}
	}
	public static class Point {
		double x, y;
		
		Point(double x, double y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static int[] parent;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		double answer = 0;
		int N = stoi(br.readLine());
		parent = new int[N];
		Point[] point = new Point[N];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			point[i] = new Point(stod(st.nextToken()), stod(st.nextToken()));
		}
		
		ArrayList<Edge> list = new ArrayList<>();
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(i == j) continue;
				else {
					list.add(new Edge(i, j, d(point[i].x, point[j].x, point[i].y, point[j].y)));
				}
			}
		}
		
		Collections.sort(list);
		
		for(int i = 0; i < N; i++) parent[i] = i;
		
		for(int i = 0; i < list.size(); i++) {
			Edge e = list.get(i);
			
			if(find(e.start) != find(e.end)) {
				union(e.start, e.end);
				answer += e.w;
			}
		}
		
		System.out.println(answer);
	}
	
	public static double d(double x1, double x2, double y1, double y2) {
		double tmp = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
		
		return Math.sqrt(tmp);
	}
	
	public static void union(int a, int b) {
		a = find(a);
		b = find(b);
		
		if(a > b) {
			parent[a] = b;
		}
		else {
			parent[b] = a;
		}
	}
	
	public static int find(int x) {
		if(parent[x] == x) return x;
		else return find(parent[x]);
	}
}

후기

크루스칼 알고리즘과 Union Find 문제는 어떤 문제에서 사용하는지는 알지만 함수 작성과 알고리즘이 조금 익숙하지 않아 연습을 많이 해봐야겠다.