출처
https://school.programmers.co.kr/learn/courses/30/lessons/42861
문제
가장 적은 비용을 들여 모든 섬 사이에 다리를 놓는 문제입니다.
최소 신장트리 문제이며, 해결법으로는 크루스칼 알고리즘과 프림 알고리즘이 있습니다.
크루스칼, 프림 알고리즘이란?
크루스칼 프림 알고리즘은 최소 신장 트리(Minimum spanning tree)를 구하는 대표적인 알고리즘 입니다.
MST란?
신장트리(Spanning Tree)는 무방향 그래프 G(V, E)에서 E에 속한 간선들로 사이클을 포함하지 않으면서 모든 정점 V를 연결한 부분 그래프를 말합니다. 그래프에서 신장 트리는 여러 형태로 존재 할 수 있으며, 특징으로는 N개의 정점을 갖는 그래프에서 신장트리의 간선은 n-1개이며 사이클을 갖지 않는다는 특징이 있습니다.
그중 MST란 최소 비용을 가지는 신장 트리를 말하며, 무방향 그래프들 사이에서 간선에 가중치가 주어진 경우, 여러개의 신장 트리중 간선들의 가중치 합이 최소인 트리입니다.
효율적인 망 설계 등에 이용될 수 있다고 합니다.
Kruskal 알고리즘
크루스칼 알고리즘은 위에 말한 MST를 구하는 알고리즘이며, greedy하게 (결정의 순간마다 최선의 결정을 함으로서 최종적인 해답에 도달) 모든 정점을 최소 비용으로 연결합니다.
크루스칼 알고리즘의 핵심은 모든 간선을 가중치 기준으로 오름차순 정렬 -> 이 간선들을 순서대로 모든 정점이 연결될때 까지 연결한다는 것입니다.
Union-find 알고리즘을 이용하여 구현할 수 있고, 이를 통해 사이클이 형성되지 않으면서 모든 정점을 연결할 수 있습니다.
Union-find 알고리즘이란?
대표적인 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다.
- 상호 배타적 집합(Disjoint-set)라고도 합니다.
- 여러 노드가 존재할 때, 두개의 노드를 선택하여 현재 두 노드가 서로 같은 그래프에 속하는지 판별합니다.
- 2가지 연산으로 이루어져 있습니다
- Find: x가 어떤 집합에 포함되어 있는지 찾는 연산
- Union: x와 y가 포함되어 있는 집합을 합치는 연산
자세한 동작 원리가 궁금하다면 나동빈님의 블로그를 참고하여 보시면 좋을 것 같습니다.
동작 방식
- 그래프의 간선들을 가중치 기준 오름차순으로 정렬한다.
- 정렬된 간선 리스트를 순서대로 선택하여, 간선의 정점들을 연결한다. 이때 정점을 연결하는 것은 Union-Find의 Union으로 구현한다.
- 만약 간선의 두 정점 a,b가 연결되어 있다면 스킵한다.
- 위의 과정을 반복하여 최소 비용의 간선들만 이용하여 모든 정점이 연결된다.
크루스칼을 이용한 풀이
import java.util.*;
class Solution {
private int[] parent;
public int find(int a) {
if(parent[a] == a) return a;
else return parent[a] = find(parent[a]);
}
public void union(int a, int b) {
a = find(a);
b = find(b);
if(a != b) {
parent[b] = a;
}
}
public int solution(int n, int[][] costs) {
int answer = 0;
parent = new int[n];
for(int i = 0; i < n; i++) {
parent[i] = i;
}
Arrays.sort(costs, (o1, o2) -> o1[2] - o2[2]);
//Kruskal Algorithm
for(int i = 0; i < costs.length; i++) {
if(find(costs[i][0]) != find(costs[i][1])) {
union(costs[i][0], costs[i][1]);
answer += costs[i][2];
}
}
return answer;
}
}Prim 알고리즘
프림 알고리즘도 위에 말한 최소 신장트리를 구하는 알고리즘 입니다. 프림은 임의의 시작점에서 현재까지 연결된 정점들에서 연결되지 않은 정점들에 대해, 가장 가중치가 작은 정점을 연결하는 정점 선택 기반으로 동작합니다.
프림의 핵심은 트리 집합을 단계적으로 확장하는 것이고, 새로운 정점을 연결할때 마다 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선을 추가해주어야 합니다.PriorityQueue를 이용한 최소 힙으로 구현할 수 있고, 다익스트라 알고리즘과 유사한 구현방식을 가집니다.
동작 방식
- 임의의 정점을 시작점으로 선택한다.
- 시작점에서 갈 수 있는 정점 중 가장 가중치가 작은 정점을 연결한다.
- 2번 과정에서 어떠한 정점과 연결되었는데, 이렇게 연결된 정점들의 집합을 x집합이라고 하면 x집합에서 갈 수 있는 x집합에 포함되어 있지 않은 정점들에 대해 가중치가 가장 작은 정점들을 연결한다.
- x 집합의 크기는 점점 커지며, 위 과정을 모든 정점이 연결될때 까지 반복한다.
프림을 이용한 풀이
import java.util.*;
class Solution {
public class Point implements Comparable<Point> {
int node, cost;
public Point(int node, int cost) {
this.node = node;
this.cost = cost;
}
@Override
public int compareTo(Point o) {
return this.cost - o.cost;
}
}
public List<List<Point>> map = new ArrayList<>();
public int solution(int n, int[][] costs) {
int answer = 0;
for(int i = 0; i < n; i++) {
map.add(new ArrayList<>());
}
for (int i = 0; i < costs.length; i++) {
int from = costs[i][0];
int to = costs[i][1];
int val = costs[i][2];
map.get(from).add(new Point(to, val));
map.get(to).add(new Point(from, val));
}
//Prim Algorithm
boolean[] visited = new boolean[n];
PriorityQueue<Point> queue = new PriorityQueue<>();
queue.add(new Point(0, 0));
while(!queue.isEmpty()) {
Point cur = queue.poll();
if(visited[cur.node]) continue;
visited[cur.node] = true;
answer += cur.cost;
for(int i = 0; i < map.get(cur.node).size(); i++) {
int next = map.get(cur.node).get(i).node;
int cost = map.get(cur.node).get(i).cost;
if(visited[next]) continue;
queue.add(new Point(next, cost));
}
}
return answer;
}
}출처 및 참고
