[골드4] 1197. 최소 스패닝 트리 (Java)

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

SSAFY 수업 복습해버리기~~

---

※  문제를 요약하면 아래와 같습니다.

▶ 그래프가 주어졌을 때, 그 긏래프의 최소 스패닝 트리를 구하는 프로그램 작성

▶ 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리

      ex ) 스패닝 트리 예시

▶  Input : 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어짐, 이후 E개의 줄에 연결된 두 정점과 가중치 입력

▶  Output : 최소 스패닝 트리의 가중치 출력

---

◈ Input - 1

3 3
1 2 1
2 3 2
1 3 3

◈ Output - 1

3

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 크루스칼 알고리즘 활용

    1. 연결된 두 노드의 간선의 가중치 및 두 노드의 값을 2차원 배열 형태로 저장

          => i 번째 간선의 0번은 시작 노드   == arr[i][0]

          => i 번째 간선의 1번은 끝 노드  == arr[i][1]

          => i 번쨰 간선의 가중치 값  == arr[i][2]

    2. 가중치 값을 기준으로 2차원 배열을 정렬

         => 최소 가중치를 갖는 노드 정보 부터 연결해준다아.

    3. 집합의 정보를 표시해주는 V사이즈의 배열 선언

    4. 정렬된 2차원 배열에서 최소 가중치를 갖는 노드들 탐색

       4-1. 같은 집합이 아닐 경우 == 시작 노드와 끝노드가 연결 되어 있지 않다 == 두 노드의 루트노드가 다르다

       4-2. 연결 == 집합의 정보를 변경 == 끝 노드의 루트 노드를 시작 노드로 설정

       4-3. 총 가중치에 더하여 저장

       4-4. 4-1의 케이스가 아닐 경우 == 이미 두 노드는 연결되어 있다 == 무시

       4-5. 스패닝 트리가 V-1 크기를 가질 때 까지 4-1~4-4 반복

---

import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	static int[] narrSet;
	public static void main(String[] args) throws IOException {
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(bReader.readLine());

		int V = Integer.parseInt(st.nextToken()); // 정점의 개수
		int E = Integer.parseInt(st.nextToken()); // 간선의 개수
		
		int[][] narr = new int[E][3];
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(bReader.readLine());
			narr[i][0] = Integer.parseInt(st.nextToken())-1;
			narr[i][1] = Integer.parseInt(st.nextToken())-1;
			narr[i][2] = Integer.parseInt(st.nextToken());
			
		}

		// 1. 오름차순 정렬하구
		Arrays.sort(narr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[2] - o2[2];
			}
			
		});
		
		// 2.집합 만들어주공
		narrSet = new int[V];
		for(int i = 0; i < narrSet.length; i++)
			narrSet[i] = i;
		
		// 2.1 가중치가 낮은 노드부터 연결해주자
		// 동일한 집합내에 있으면 안되니까 연결 금지이
		int nConnect = 0;
		int nWeight = 0;
		
		for(int i = 0; i < E; i++) {
			
			int nFirstHead = find(narr[i][0]);
			int nSecondHead = find(narr[i][1]);
			
			// 같은 집합 아니면 연결해주자
			if(nFirstHead != nSecondHead) {
				union(nFirstHead, nSecondHead);
				nConnect++;
				nWeight += narr[i][2];
			}
			// 이것이 최소 스패닝 트리이다.
			if(nConnect == V-1)
				break;
		}


		bWriter.write(String.valueOf(nWeight));

		bWriter.flush();
		bWriter.close();
	}

	private static void union(int nFirstHead, int nSecondHead) {
		narrSet[nSecondHead] = nFirstHead;
	}

	static int find(int x) {
		if(x != narrSet[x])
			narrSet[x] = find(narrSet[x]);
		return narrSet[x];
	}
}

---

 

Good Luck! (피드백 감사합니다!)