가장 적은 비용으로 모든 노드를 연결하기 위한 알고리즘
그래프 이론을 통해 최소 신장 트리(Minimum Spanning Tree)를 공부해 본다.
노드(Node) = 정점 = 도시 : 그래프 상에서 동그라미에 해당하는 부분
간선(Edge) = 거리 = 비용 : 그래프 상에서 선에 해당하는 부분
(* 최소 신장 트리에서 간선의 개수 = 노드 - 1)
public class Main {
private static int[] parent;
private static class Edge implements Comparable<Edge> {
int node1;
int node2;
int weight;
public Edge(int node1, int node2, int weight) {
this.node1 = node1;
this.node2 = node2;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return weight - o.weight;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
parent = new int[V + 1];
Edge[] edges = new Edge[E];
// 각각의 노드들이 자신을 바라보도록 설정한다.
// 유니온 파인드 초기화
for (int i = 1; i < parent.length; i++) {
parent[i] = i;
}
// Edge들을 배열에 넣어준다.
for (int i = 0; i < edges.length; i++) {
st = new StringTokenizer(br.readLine());
int node1 = Integer.parseInt(st.nextToken());
int node2 = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
edges[i] = new Edge(node1, node2, weight);
}
// 클래스를 comparable인터페이스로 정렬기준을 오버라이딩 해놨기 때문에 가중치 기준으로 오름차순 정렬된다.
Arrays.sort(edges);
int res = 0;
for (int i = 0; i < edges.length; i++) {
Edge edge = edges[i];
int node1 = edge.node1;
int node2 = edge.node2;
int weight = edge.weight;
if (find(node1) != find(node2)) {
union(node1, node2);
res += weight;
}
}
System.out.println(res);
}
private static int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
private static void union(int a, int b) {
int root1 = find(a);
int root2 = find(b);
if (root1 > root2) {
parent[root1] = root2;
} else {
parent[root2] = root1;
}
}
}