[백준] 단계별로 풀어보기(단계:31, 최소 신장 트리,JAVA)1197번, 최소 스패닝 트리

문제 링크

1197번: 최소 스패닝 트리

---

주의사항

• 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-2	2-3	1-3
1	2	3

 

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

1	2	3
1	2	3

 

1-2 선분 탐색

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

 

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

1	2	3
1	1	3

 

2-3 선분 탐색

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

 

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

1	2	3
1	1	1

 

1-3 선분 탐색

1과 3의 Root Node는 같아서 사이클 형성 O, 선분을 이용 X

 

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

1	2	3
1	1	1

 

사용된 선분 1-2, 2-3의 가중치의 합은 = 3

 

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

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 사용하여 선분에 대한 정보를 저장합니다.
• 선분에 대하여 Arrays.sort를 이용하여 가중치 기준 오름차순 정렬하였습니다.
• 루트 노드가 같은지 확인 및 변경하는 union함수를 이용하여 사이클이 생기지 않는 선분의 가중치들을 더하였습니다.
• BufferedWriter에 최소 신장 트리의 가중치 합을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

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

결과 코드

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

public class Main{
	//선분에 대한 정보 생성자
	static class node{
		int point1, point2;
		long value;
		public node(int point1,int point2, long value) {
			super();
			this.point1 = point1;
			this.point2 = point2;
			this.value = value;
		}
	}
	static int V,E;
	static int[] root;	//루트 노드 정보 저장 배열
	static long result = 0; 
	static node[] graph;	//입력되는 선분의 값 저장 배열
	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()," ");
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		graph = new node[E];
		root = new int[V+1];
		visited = new boolean[V+1];
        	//루트 노드 초기화
		for(int i=0;i<=V;i++) 
			root[i] = i;
			//그래프의 값 저장	
		for(int i=0;i<E;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			long C = Long.parseLong(st.nextToken());
			graph[i] = new node(A,B,C);
		}
        	//선분 가중치 기준 오름차순 정렬
		Arrays.sort(graph, new Comparator<node>() {
			@Override
			public int compare(node o1, node o2) {
				return (int)(o1.value - o2.value);
			}
		});
        	//선분들 탐색
		for(int i=0;i<E;i++) {
        		//루트 노드 같은지 확인
			if(!union(graph[i].point1, graph[i].point2)) {
				result += graph[i].value;	//같으면 가중치 더하기
			}
		}
		bw.write(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;		//루트 노드가 같다.
	}
}