[백준] 4386번 별자리 만들기(Java) - 세무민의 코딩일기

이번 포스팅에서 다룰 문제는 별자리 만들기 입니다.

---

1. 문제

---

2. 입출력 및 예시 

---

3. 문제 풀이

이번 문제에서 포인트는 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있다는 말이다.

이 말은 즉 그래프 형태이면서 간접적으로 연결되어 있다는 것은 부모가 연결되어 있으면 연결되어 있는 구조이다.

이 문제는 최소 스패닝 트리 문제와 동일하다.

따라서 Kruskal-Mst 알고리즘을 이용해서 문제를 풀면 된다.

그렇지만 문제를 풀다보면 기존에는 결과값을 주었지만 이 문제는 주지 않았다. 

그 말은 해당 정점들의 간선 길이를 내가 직접 구해야 한다는 말이다. 

아래의 그림을 보면서 한번 이해해보자.

위의 예시대로 그림을 그려봤다. 

정점들을 그린 뒤 간선을 하나씩 이어봤다. 

간선을 이어봤다면 이제 어느정도 감이 왔을 것이다. 

가장 짧은 간선을 구하는 방법은 피타고라스의 정의를 이용하면 된다는 말이다. 

따라서 이번 문제에서는 피타고라스의 정의를 이용하여 풀었다. 

---

4. 코드 및 결과

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
/**
 * [별자리 만들기]
 * Q.별자리를 이루는 선은 서로 다른 두별을 일직선으로 이은 형태이다 -> 2개의 정점을 1개의 간선으로 이어준다.
 * Q.모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. -> 1-2 / 2-3 => 1-3 
 * A. 피타고라스 정리를 사용하면 됨 
 * */

public class backjoon_4386 {
	static int[] parent;
	static ArrayList<starNode> nodeList;
	static ArrayList<stars> checkList;
	
	
	// 피타고라스 정의 이용
	public static double Pythagoras(stars s1, stars s2) {
		double x = s1.frist - s2.frist;
		double y = s1.end - s2.end;
		return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
	}

    // union-find 선언
	public static int find(int answer) {
		if(parent[answer] == answer) {
			return answer;
		} else {
			return parent[answer] = find(parent[answer]);
		}
	}
	
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		 
		if(y != x) parent[y] = x;
	}
	
    // kruskal 이용
	public static double kruskal(int numbers) {
		parent = new int[numbers + 1];
	
		for(int i = 1; i <= numbers; i++) {
			parent[i] = i;
		}
		
		Collections.sort(nodeList);
		
		double answer = 0;
		for(starNode star : nodeList){
			starNode nodes = star;

			if(find(nodes.fristStar) != find(nodes.endStar)){
				answer += nodes.result; 
				union(nodes.fristStar, nodes.endStar);
			}
			
		}
		
		// 소숫점 2자리
		double result = Double.parseDouble(String.format("%.2f", answer));
		return result;
	}
	
    // 메인
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer stringTk;
		
		int numbers = Integer.parseInt(reader.readLine());
		nodeList = new ArrayList<starNode>();
		checkList = new ArrayList<stars>();
		
		for(int i = 0; i < numbers; i++) {
			stringTk = new StringTokenizer(reader.readLine());
			double fristPoint = Double.parseDouble(stringTk.nextToken());
			double endPoint = Double.parseDouble(stringTk.nextToken());
			
			checkList.add(new stars(i, fristPoint, endPoint));
		}
        
        
        
		for(int i = 0; i < numbers; i++) {
			for (int j = i + 1; j < numbers; j++) {
				double nums = Pythagoras(checkList.get(i), checkList.get(j));
				
				nodeList.add(new starNode(checkList.get(i).n, checkList.get(j).n, nums));
			}
		}
		
		double result = kruskal(numbers);
		
		writer.write(result + "\n");
		writer.flush();
		writer.close();
		reader.close();
		
		
	}
}

/**
* 클래스 선언부
**/
class stars {
	int n;
	double frist;
	double end;
	
	stars(int n, double frist, double end){
		this.end = end;
		this.frist = frist;
		this.n = n;
	}
	
}
class starNode implements Comparable<starNode>{
	int fristStar;
	int endStar;
	double result;
	
	starNode(int fristStar, int endStar, double result){
		this.fristStar = fristStar;
		this.endStar = endStar;
		this.result = result;
	}

	@Override
	public int compareTo(starNode star) {
		// 오름차순	
		if(result < star.result) return -1;
		else return 1;
	}
}

기본 Kruskal 로직과 동일하며 해당 로직에서는 피타고라스에 대한 공식만 추가했다. 

그래서 처음에 입력받을 때 위치와 x, y값을 받아서 피타고라스로 가장 짧은 선을 구해준 뒤 

해당 값을 이용해서 최소값을 구해주면 되는 문제이다.

GitHub

GitHub - sg-moomin/programmersStudy

상세한 코드는 GitHub에 동일하게 구성되어 있습니다. 

결과는 성공! 

---

이번 포스팅에서도 최소 스패닝 트리에 대한 문제를 풀었는데 익숙해질 때까지 계속 풀어볼 생각입니다.

다음 포스팅에서는 더 좋은 정보로 찾아오겠습니다.