최소 스패닝 트리
https://www.acmicpc.net/problem/1197
문제
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
입력
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.
그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.
출력
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
문제 풀이 방법 및 해설
이 번에 풀어본 문제의 종류는 MST(최소신장트리)이다. 신장 트리란 주어진 그래프의 부분 그래프 중 모든 정점을 포함하는 트리를 말한다. 여기서 MST란 이를 최소한의 비용(기존 간선)으로 이루어진 그래프이다.
MST 알고리즘을 풀이는 2가지 대표 알고리즘이 있다. 크루스칼 알고리즘과 프림 알고리즘이 존재하는데 두 개 전부 풀이를 해보겠다.
크루스칼 알고리즘은 유니온 파인드라는 알고리즘을 사용한다. 유니온 파인드는 서로의 집합을 확인하는 알고리즘이다. parent[] 배열을 통해 최상위를 확인하여 서로 같은 집단인지 확인하는 알고리즘이다. 프림 알고리즘은 유니온 파인드 알고리즘을 몰라도 구현할 수 있다. 우선순위 큐를 사용하여 구현을 하면 된다.
풀이 코드
크루스칼
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
public static class Node{
int v1;
int v2;
int value;
public Node(int v1, int v2, int value) {
this.v1 = v1;
this.v2 = v2;
this.value = value;
}
}
static int[] parent;
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];
PriorityQueue<Node> pq = new PriorityQueue<>((p1, p2) -> p1.value - p2.value);
for(int i = 1 ; i <= V ; i++){
parent[i] = -1;
}
for(int i = 0 ; i < E ; i++){
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
int value = Integer.parseInt(st.nextToken());
pq.offer(new Node(v1,v2,value));
}
int count = 0;
int answer = 0;
while(true){
if(count == V - 1){
break;
}
Node node = pq.poll();
if(isSame(node.v1, node.v2)) continue;
union(node.v1, node.v2);
count++;
answer += node.value;
}
System.out.println(answer);
}
public static int find(int value){
if(parent[value] < 0){
return value;
}
return parent[value] = find(parent[value]);
}
public static void union(int a, int b){
a = find(a);
b= find(b);
if(a < b){
parent[a] += parent[b];
parent[b] = a;
}else{
parent[b] += parent[a];
parent[a] = b;
}
}
public static boolean isSame(int a, int b){
return find(a) == find(b);
}
}프림
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static class Node{
int idx;
int value;
public Node(int idx, int value) {
this.idx = idx;
this.value = value;
}
}
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());
boolean[] check = new boolean[V+1];
ArrayList<Node>[] arr = new ArrayList[V+1];
for(int i = 1 ; i <= V ; i++){
arr[i] = new ArrayList<>();
}
for(int i = 0 ; i < E ; i++){
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
int value = Integer.parseInt(st.nextToken());
arr[v1].add(new Node(v2, value));
arr[v2].add(new Node(v1, value));
}
PriorityQueue<Node> q = new PriorityQueue<>((p1, p2) -> p1.value - p2.value);
q.offer(new Node(1, 0));
int answer = 0;
while(!q.isEmpty()){
Node node = q.poll();
if(check[node.idx]) continue;
else check[node.idx] = true;
answer += node.value;
for(Node value : arr[node.idx]){
if(!check[value.idx]){
q.offer(value);
}
}
}
System.out.println(answer);
}
}