최소 신장 트리, MST
최소 신장 트리는 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리로 두 정점 사이의 최소 비용의 경로를 찾을 때 사용된다.
이 때 정점의 개수가 N이라면, 간선의 개수는 N(N-1)이 된다. 방향이 있는 경우는 N(N-1)/2 이다.
최소의 비용으로 모든 점을 다 이을 때 이 알고리즘을 사용해서 문제를 푼다! ( 그러나 임의의 두 점간의 거리가 최소라는 보장은 없다.)
최소 신장 트리와 관련된 알고리즘을 잘 이해하기 위해서 이 문제를 푸는 것을 추천한다! 가장 기본적인 MST 알고리즘 문제 (이름부터,,) 이다.
Kruskal 알고리즘
크루스칼 알고리즘은 간선을 하나씩 선택해서 MST를 찾는 간선 중심 알고리즘이다. 간선정보가 필요하기 때문에 보통 Edge Class를 생성하여 문제를 푼다.
알고리즘 순서
- 간선리스트를 작성하고 모든 간선을 가중치에 따라 오름차순 정렬을 한다.
- 두 정점을 연결하고 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다. -> 사이클이 발생하는 경우 다음으로 가중치가 낮은 간선 선택!
- N개의 정점이 존재하는 경우 N-1개의 정점이 선택될때까지 2번을 반복한다.
BOJ 1197 최소 스패닝 트리 (ver.크루스칼 알고리즘)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static class Edge implements Comparable<Edge>{
int from;
int to;
int weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
// TODO Auto-generated method stub
return this.weight - o.weight;
}
}
static int find(int a) {
if(parents[a]==a) {
return a;
}
return parents[a] = find(parents[a]);
}
static boolean union(int a,int b) {
int aRoot = find(a);
int bRoot = find(b);
if(aRoot==bRoot) {
return false;
}
parents[bRoot] = aRoot;
return true;
}
static int V,E;
static int[] parents;
static Edge[] EdgeList;
public static void main(String[] args)throws Exception {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
parents = new int[V+1];
EdgeList = new Edge[E];
for(int i=0; i<E; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
EdgeList[i] = new Edge(from,to,weight);
}
Arrays.sort(EdgeList);
for(int i=1; i<=V; i++) {
parents[i] = i;
}
int result = 0;
int count = 0;
for (Edge e : EdgeList) {
// 싸이클이 발생한다면
if(union(e.from,e.to)) {
result += e.weight;
if(++count==V-1) {
break;
}
}
}
System.out.println(result);
}
}우선순위큐를 사용하여 문제를 푼 예시
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static class Edge implements Comparable<Edge>{
int from;
int to;
int weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
// TODO Auto-generated method stub
return this.weight - o.weight;
}
}
static int find(int a) {
if(parents[a]==a) {
return a;
}
return parents[a] = find(parents[a]);
}
static boolean union(int a,int b) {
int aRoot = find(a);
int bRoot = find(b);
if(aRoot==bRoot) {
return false;
}
parents[bRoot] = aRoot;
return true;
}
static int V,E;
static int[] parents;
static PriorityQueue<Edge> pq = new PriorityQueue<>();
public static void main(String[] args)throws Exception {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
parents = new int[V+1];
for(int i=0; i<E; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
pq.add(new Edge(from,to,weight));
}
for(int i=1; i<=V; i++) {
parents[i] = i;
}
int result = 0;
int count = 0;
while(!pq.isEmpty()) {
Edge e = pq.poll();
if(union(e.from,e.to)) {
result += e.weight;
if(++count==V-1) {
break;
}
}
}
System.out.println(result);
}
}처음에 크루스칼 알고리즘 문제를 풀었을 때 우선순위큐를 사용하는 것이 아닌 배열을 사용해서 풀었는데 우선순위큐를 사용한것이 훨씬 빨랐다..!
우선순위큐를 사용하지 않았을 때
| 메모리 | 시간 |
|---|---|
| 49444kb | 656ms |
우선순위큐를 사용하였을 때
| 메모리 | 시간 |
|---|---|
| 45716kb | 424ms |
Prim 알고리즘
하나의 정점에서 연결된 간선들 중에서 하나씩 선택하면서 MST를 선택하는 방식.
알고리즘 순서
- 임의의 정점을 하나 선택한다.
- 선택한 정점과 인접하는 정점들 중의 최소의 비용의 간선이 존재하는 정점을 선택
- 모든 정점이 선택될 때 까지 1,2번 과정 반복
BOJ 1197 최소 스패닝 트리 (ver.프림 알고리즘)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int V;
static int E;
static boolean[] visited;
static ArrayList<Node>[] arr;
static PriorityQueue<Node> pq = new PriorityQueue<>();
static class Node implements Comparable<Node>{
int vertex;
int weight;
public Node(int vertex,int weight) {
this.vertex = vertex;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return this.weight - o.weight;
}
}
public static void main(String[] args) throws Exception{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
visited = new boolean[V+1];
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 from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
arr[from].add(new Node(to,weight));
arr[to].add(new Node(from,weight));
}
int answer = 0;
int count = 0;
// 1번 노드 부터 탐색 시작
pq.add(new Node(1,0));
while(!pq.isEmpty()) {
Node cur = pq.poll();
if(visited[cur.vertex]) continue;
visited[cur.vertex] = true;
answer += cur.weight;
for (Node node : arr[cur.vertex]) {
if(!visited[node.vertex]) {
pq.add(node);
}
}
// 모든 정점이 선택되었다면 break
if(++count == V) break;
}
System.out.println(answer);
}
}개인적으로 크루스칼이 더 사용하기 편한것(?) 같다. 프림은 정점 위주의 알고리즘이고 크루스칼은 간선 위주의 알고리즘인데 간선의 개수 적으면 보통 크루스칼, 많으면 프림을 사용한다고 한다. 사실 많다는 기준을 잘 모르겠어서 보통 크루스칼을 사용하기는 한다. 임의의 정점을 주면 프림으로 풀고 안주면 크루스칼로 풀어야겠다!
멋쟁이 개발자가 될꺼야