[백준] 단계별로 풀어보기(단계:31, 최소 신장 트리,JAVA)1774번, 우주신과의 교감

문제 링크

1774번: 우주신과의 교감

---

주의사항

• 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를 이용하여 사이클이 발생하는지 확인하여 최소 신장 트리를 완성하였습니다.

 

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

 

이미 연결된 통로들을 먼저 Union-Find를 진행해주어서 Root Node를 변경하였습니다.

 

이후 남은 통로들을 이용해서 Union-Find를 이용해서 최소 신장 트리를 만들고 그에 대한 가중치의 합을 출력하였습니다.

 

우주신과 우주신 사이의 거리 구하는 공식

 

예제입력1

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

1 - 2. (1, 1) -> (3, 1) , 길이 : 2

1 - 3. (1, 1) -> (2, 3) , 길이 : 루트 5

1 - 4. (1, 1) -> (4, 3) , 길이 : 루트 13

2 - 3. (3, 1) -> (2, 3) , 길이 : 루트 5

2 - 4. (3, 1) -> (4, 3) , 길이 : 루트 5

3 - 4. (2, 3) -> (4, 3) , 길이 : 2

 

※Union-Find를 이용하기 위해서 길이(가중치) 기준 오름차순 정렬을 진행합니다.

 

1 - 2. (1, 1) -> (3, 1) , 길이 : 2

3 - 4. (2, 3) -> (4, 3) , 길이 : 2

1 - 3. (1, 1) -> (2, 3) , 길이 : 루트 5

2 - 3. (3, 1) -> (2, 3) , 길이 : 루트 5

2 - 4. (3, 1) -> (4, 3) , 길이 : 루트 5

1 - 4. (1, 1) -> (4, 3) , 길이 : 루트 13

 

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

1	2	3	4
1	2	3	4

 

이미 연결된 통로 1 - 4

 

1	2	3	4
1	1	3	1

1 - 2. 탐색

1과 2의 Root Node는 다르기 때문에 사이클 형성 X, 선분을 이용

 

1	2	3	4
1	1	3	1

 

3 - 4. 탐색

3과 4의 Root Node는 다르기 때문에 사이클 형성 X, 선분을 이용

 

1	2	3	4
1	1	1	1

 

이후 다른 통로들을 탐색해도 모든 루트 노드가 동일하기 때문에 이용할 수 없습니다.

 

사용되는 통로 1 - 2 , 3 - 4의 가중치의 합은 = 2 + 2  = 4.00

 

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

 

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

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

 

결과 코드

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

public class Main{
	//우주신들의 위치 생성자
	static class Gods{
		int x, y;
		public Gods(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
	}
    	//우주신 통로 관련 생성자
	static class line{
		int g1, g2;
		double width;
		public line(int g1, int g2, double width) {
			super();
			this.g1 = g1;
			this.g2 = g2;
			this.width = width;
		}
		
	}
	static int N,M;
	static ArrayList<Gods> god = new ArrayList<>();	//우주신들의 좌표 저장
	static ArrayList<line> con = new ArrayList<>();	//통로 저장
	static int[] root;	//Root Node 배열
	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 = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		root = new int[N+1];
        	//Root Node 초기화
		for(int i=0;i<=N;i++)
			root[i] = i;
            	//우주신들의 위치 저장
		for(int i=0;i<N;i++) {
			st =new StringTokenizer(br.readLine()," ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			god.add(new Gods(x,y));
		}
        	//이미 연결된 통로 Union-Find 진행
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			union(x,y);
		}
        	//모든 경우의 통로 구하기
		for(int i=0;i<N;i++) {
			for(int j=i+1;j<N;j++) 
				con.add(new line(i+1,j+1,widthCal(god.get(i),god.get(j))));
		}
        	//통로 길이(가중치) 기준 오름차순 정렬
		Collections.sort(con,new Comparator<line>() {
			@Override
			public int compare(line c1, line c2) {
				if(c1.width >= c2.width)
					return 1;
				else 
					return -1;
			}
		});
		double result = 0;
        	//각 통로 Union-Find로 최소 신장 트리 및 가중치 합 구하기
		for(int i=0;i<con.size();i++) {
			int g1 = con.get(i).g1;
			int g2 = con.get(i).g2;
			if(!union(g1,g2))
				result += con.get(i).width;
		}
        	//소수점 2자리까지 나오도록 형식 변환하기
		DecimalFormat df = new DecimalFormat(".00");
		bw.write(df.format(result) + "\n");	//가중치의 합 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//루트 노드 찾는 함수
	static int find(int n) {
		if(root[n] == 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;
	}
    	//우주신끼리의 거리 구하는 함수
	static double widthCal(Gods g1, Gods g2) {
		return Math.sqrt(Math.pow(g1.x-g2.x, 2) + Math.pow(g1.y-g2.y, 2));
	}
}