[백준] 단계별로 풀어보기(단계:31, 최소 신장 트리,JAVA)4386번, 별자리 만들기

문제 링크

4386번: 별자리 만들기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

최소 신장 트리

신장 트리 : 어떤 그래프에 대하여 모든 꼭짓점을 포함하는부분 그래프입니다.

 

최소 신장 트리 : 신장 트리에서 최소의 가중치를 가지는 부분 그래프입니다. 

Minimum spanning tree - Wikipedia

이 문제에 핵심은

1. 입력되는 값은 그래프 관련 값들입니다.

2. 최소 신장 트리의 가중치 값을 결과로 출력합니다.

 

최소 신장 트리를 구하기 위해서 Union-Find와 Greedy알고리즘을 이용하여 구현하였습니다.

Union Find - 나무위키

 

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

 

 

Greedy알고리즘을 이용하여 가중치가 낮은 선분부터 탐색을 시작합니다.

 

선분을 탐색할 때 Union-Find를 이용하여 사이클이 발생하는지 확인하여 최소 신장 트리를 완성하였습니다.

 

선분에 대한 정보를 얻기 위해서 각 별에서 다른 별의 선분의 길이를 구해서 리스트에 저장하였습니다.

 

별과 별 사이의 거리 구하는 공식

 

예제입력1

각 별의 위치에서 발생할 수 있는 선분들

(1.0, 1.0) -> (2.0, 2.0) , 길이 : 루트 2

(1.0, 1.0) -> (2.0, 4.0) , 길이 : 루트 10

(2.0, 2.0) -> (2.0, 4.0) , 길이 : 2

 

※입력값에서는 가중치를 오름차순으로 받았지만 실제로는 가중치 기준 오름차순 정렬을 진행해야 합니다.

 

오름차순 정렬한 선분들

(1.0, 1.0) -> (2.0, 2.0)	(2.0, 2.0) -> (2.0, 4.0)	(1.0, 1.0) -> (2.0, 4.0)
루트 2	2	루트 10

 

Union-Find에 사용할 Root Node 가리키는 값

1번째 선분	2번째 선분	3번째 선분
1	2	3

 

(1.0, 1.0) -> (2.0, 2.0) 선분 탐색

(1.0, 1.0) -> (2.0, 2.0)의 Root Node는 다르기 때문에 사이클 형성 X, 선분을 이용

 

1번째 선분	2번째 선분	3번째 선분
1	1	3

 

(2.0, 2.0) -> (2.0, 4.0) 선분 탐색

(2.0, 2.0) -> (2.0, 4.0)의 Root Node는 다르기 때문에 사이클 형성 X, 선분을 이용

 

1번째 선분	2번째 선분	3번째 선분
1	1	1

 

(1.0, 1.0) -> (2.0, 4.0) 선분 탐색

(1.0, 1.0) -> (2.0, 4.0)의 Root Node는 같아서 사이클 형성 O, 선분을 이용 X

 

1번째 선분	2번째 선분	3번째 선분
1	1	1

 

사용된 선분 (1.0, 1.0) -> (2.0, 2.0) , (2.0, 2.0) -> (2.0, 4.0)의 가중치의 합은 = 2 + 루트 2  = 3.41.....

 

최소 신장 트리의 가중치의 합(3.41...)을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 사용하여 별에 x좌표와 y좌표를 저장합니다.
• 각 별에 대하여 만들 수 있는 선분을 만들며 가중치는 별 사이의 거리입니다.
• 선분에 대하여 Collections.sort를 이용하여 길이(가중치) 기준 오름차순하였습니다.
• 루트 노드가 같은지 확인 및 변경하는 union함수를 이용하여 사이클이 생기지 않는 선분의 가중치들을 더하였습니다.
• BufferedWriter에 최소 신장 트리의 가중치 합을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• widthCal함수는 2개의 별의 거리를 구하는 함수입니다.
• find함수는 루트 노드의 값을 구하는 재귀 함수입니다.
• union함수는 루트 노드가 같은지 확인 및 변경하는 함수입니다.

결과 코드

import java.io.*;
import java.util.*;

public class Main{
		//별의 위치 정보 생성자
	static class point{
		double x, y;
		public point(double x, double y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
    	//선분에 대한 정보 생성자
	static class line{
		int star1, star2;
		double width;
		public line(int star1, int star2, double width) {
			super();
			this.star1 = star1;
			this.star2 = star2;
			this.width = width;
		}
	}
	static int n;
	static double result = 0;
	static int[] root;	//루트 노드
	static point[] star;	//별의 위치
	static ArrayList<line> list = new ArrayList<>();	//선분 저장 리스트
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		star = new point[n];
		root = new int[n];
        	//별의 위치 저장
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine()," ");
			star[i] = new point(Float.parseFloat(st.nextToken()),Float.parseFloat(st.nextToken()));
		}
        	//선분 정보 저장
		for(int i=0;i<n;i++) {
			for(int j=i+1;j<n;j++) 
				list.add(new line(i,j,widthCal(star[i],star[j])));		
		}
        	//선분 길이(가중치) 기준 오름차순 정렬
		Collections.sort(list,new Comparator<line>() {
			@Override
			public int compare(line o1, line o2) {
				return (int)(o1.width-o2.width);
			}
		});
        	//루트 노드 초기화
		for(int i=0;i<n;i++)
			root[i] = i;
			//선분에 대한 최소 신장 트리 가중치 합 구하기
		for(int i=0;i<list.size();i++) {
			if(!union(list.get(i).star1, list.get(i).star2))
				result += list.get(i).width;
		}
		bw.write(result + "\n");	//가중치 합 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
		
	}
    	//루트 노드 찾는 함수
	static int find(int n) {
		if(n==root[n])
			return n;
		return root[n] = find(root[n]);
	}
    	//루트 노드 비교 및 변경 함수
	static boolean union(int a, int b) {
		int x = find(a);
		int y = find(b);
		if(x!=y) {
			if(x<y)
				root[y] = x;
			else
				root[x] = y;
			return false;
		}
		return true;
	}
    	//2개의 별의 거리 구하는 함수
	static double widthCal(point star1, point star2) {
		return Math.sqrt(Math.pow(star1.x-star2.x, 2) + Math.pow(star1.y-star2.y, 2));
	}
}