[SWEA] 최소 스패닝 트리

Posted on | In |

문제 보러가기

제한사항

이외의 제한사항은 없다.

첫번째 생각

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

JAVA Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Solution {
	static int N, E; // 정점 수, 간선 수
	static int[] parent; // disjoint-set에서 각 정점의 부모(대표자) 정보 저장하는 배열
	static boolean[] visit; // 선택한 정점 재방문 안할 때 쓰는 배열
	static ArrayList<Edge> mst;
	static PriorityQueue<Edge> pq;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		for(int tc=1; tc<=T;tc++) {
			N = sc.nextInt();
			E = sc.nextInt();
			
			visit = new boolean[N+1];
			parent = new int[N+1];
			pq = new PriorityQueue<>(new EdgeComparator());
			mst = new ArrayList<>();
			
			for(int e=0; e<E; e++) {
				int st = sc.nextInt();
				int end = sc.nextInt();
				int value = sc.nextInt();
				pq.add(new Edge(st,end,value));// 간선들을 가중치로 정렬하는 우선순위 큐에 다 집어넣기.
			}
			
			kruskal();
			long sum = 0;
			for(int i=0; i<mst.size(); i++) {
				sum += mst.get(i).value;
			}
			System.out.println("#"+tc+" "+sum);
		}
	}
	
	static void kruskal() {
		for(int i=1; i<=N; i++) { // 일단 모든 정점들은 각각 다 대표로 만들어진다
			parent[i] = i;
		}
		
		for(int i=0; i<E; i++) {
			Edge edge = pq.poll(); // 가중치 작은 순서대로 간선이 나옴
			if(find(edge.start) == find(edge.end)) { // 간선의 대표자가 같으면 사이클이 생기므로 스킵. 
				continue;
			}
			union(edge.start, edge.end); //사이클이 안생기는 간선의 양 접점을 하나로 합병
			mst.add(edge);// 선택된 간선을 mst에 추가
		}
		
	}
	// 특정 원소가 포함된 집합의 대표자 찾기 메소드
	static int find(int n) { 
		if (parent[n] == n) {
			return n;
		}
		parent[n] = find(parent[n]); // find가 실행되는 시점의 소속집합 전체의 대표자를 부모로 기억시켜서 효율성 증가.
		return parent[n];
	}
	// n1과 n2가 소속된 두 집합을 합병하는 메소드
	static void union(int n1, int n2) { 
		int p1 = find(n1);
		int p2 = find(n2);

		if (p1 != p2) { // 두 집합의 대표자가 다른 경우 합병 진행
			parent[p1] = p2;
		}
	}

	// 우선순위 큐가 간선들을 가중치 순으로 줄세울 수 있게 해주는 비교기능 내장 클래스
	static class EdgeComparator implements Comparator<Edge> {
		@Override
		public int compare(Edge o1, Edge o2) {
			return o1.value > o2.value ? 1 : -1;
		}

	}
	
	// 하나의 간선정보를 하나의 객체에 묶기 위한 내부 클래스.
	static class Edge { 
		int start, end, value;

		Edge(int s, int e, int v) {
			start = s;
			end = e;
			value = v;
		}
	}
}