크루스칼 알고리즘 (Kruskal Algorithm) 이란 그래프 내의 모든 정점들을 가장 적은 비용(cost)으로 연결하기 위해 사용되는 알고리즘이다.
그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 사용한다. 즉, 최소 신장 트리(MST)를 구하기 위한 알고리즘이다.
크루스칼 알고리즘을 자세히 다루기 전에 신장 트리와 최소 신장 트리에 대해서 다뤄보자🏃♂️
신장 트리 (Spanning Tree)
신장 트리 (Spanning Tree)는 그래프의 최소 연결 부분 그래프를 의미한다.
- 최소 연결이란 간선의 수가 가장 적다는 것을 의미한다.
- 그래프에서 일부 간선을 선택해서 만든 트리.
- 모든 정점들이 연결 되어 있어야하고 사이클을 포함하면 안된다.
- 하나의 그래프에는 여러개의 신장 트리가 존재할 수 있다.
최소 신장 트리 (Minimum Spanning Tree)
최소 신장 트리 (Minimum Spanning Tree)는 위에서 언급한 신장 트리중에서 연결된 간선들의 가중치(cost)의 합이 최소인 트리를 의미한다.
크루스칼 알고리즘 (Kruskal Algorithm)
크루스칼 알고리즘 (Kruskal Algorithm)은 위에서 언급한 최소 신장 트리를 구하기 위한 알고리즘으로, 그리디 알고리즘 (Greedy Algorithm)의 일종이다.
⚡
그리디 알고리즘 (Greedy Algorithm) : 현재 상황에서 최선의 선택을 고르는 알고리즘
구현 과정
- 그래프의 간선들의 가중치를 오름차순으로 정렬
- 사이클을 형성하지 않는 선에서 순서대로 간선을 선택
- 선택된 간선을 MST 집합에 추가한다.
이때, 사이클의 형성 여부를 판단할 때 사용하는 방법이 있는데 그것이 바로 Union-Find 알고리즘이다.
(추가하고자 하는 간선의 양 끝 정점이 같은 집합에 속해 있는지를 판단하기 위해서!!!)
예시 문제
문제 설명
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
제한 사항
- 섬의 개수 n은 1 이상 100 이하입니다.
- costs의 길이는 ((n-1) * n) / 2이하입니다.
- 임의의 i에 대해, costs[i][0] 와 costs[i][1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i][2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
- 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
- 연결할 수 없는 섬은 주어지지 않습니다.
입출력 예
n costs return 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4
입출력 예 설명
costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.
문제 풀이
앞에서 말했던 대로 '그래프의 간선들의 가중치를 오름차순으로 정렬', 즉 costs[i][2]를 기준으로 costs를 먼저 정렬해줘야 한다.
costs.sort((a,b)=>a[2]-b[2]);그 다음에는 사이클 형성 확인을 위해 사용되는 Union-Find 알고리즘을 이 문제에 맞게 구현한다.
// 처음에는 자기 자신의 값을 부모로 가지는 배열 생성
const parent = [];
for(let i=0; i<n; i++) parent.push(i);
// 각 섬의 부모를 찾는 재귀 함수
// 만약 초기 값이 아니라면 parent[x]를 이용해 위로 올라가서 부모값 찾음
const getParent = (parent, x) => {
if(parent[x] === x) return x;
return parent[x] = getParent(parent,parent[x]);
}
// 두 섬의 부모를 하나로 합쳐준다.
// 이때 두 부모중 작은 값을 가지는 부모로 합쳐준다.
const unionParent = (parent, x, y) => {
const n1 = getParent(parent,x);
const n2 = getParent(parent,y);
if(n1<n2) return parent[n2] = n1;
else return parent[n1] = n2;
}
// 두 섬의 부모를 찾고, 부모가 같으면 true, 다르면 false return
const findParent = (parent, x, y) => {
const n1 = getParent(parent,x);
const n2 = getParent(parent,y);
if(n1===n2) return true;
else return false;
}위에서 구현한 Union-Find 알고리즘을 이용하여 이제 크루스칼 알고리즘을 구현해주면 된다.
for(const cost of costs){
// 만약 두 섬의 부모가 다르면, 즉 사이클이 형성되지 않은 상태라면
if(!findParent(parent,cost[0],cost[1])){
answer += cost[2]; // 정답에 해당 가중치를 더해준다 (오름차순으로 정렬해서 작은값 선택 가능)
unionParent(parent,cost[0],cost[1]); // 이제 두 섬은 연결되었으니 합쳐준다
}
}정답 코드
function solution(n, costs) {
let answer = 0;
const parent = [];
for(let i=0; i<n; i++) parent.push(i);
costs.sort((a,b)=>a[2]-b[2]);
const getParent = (parent, x) => {
if(parent[x] === x) return x;
return parent[x] = getParent(parent,parent[x]);
}
const unionParent = (parent, x, y) => {
const n1 = getParent(parent,x);
const n2 = getParent(parent,y);
if(n1<n2) return parent[n2] = n1;
else return parent[n1] = n2;
}
const findParent = (parent, x, y) => {
const n1 = getParent(parent,x);
const n2 = getParent(parent,y);
if(n1===n2) return true;
else return false;
}
for(const cost of costs){
if(!findParent(parent,cost[0],cost[1])){
answer += cost[2];
unionParent(parent,cost[0],cost[1]);
}
}
return answer;
}