[자료구조와 알고리즘] 크루스칼 알고리즘 : 섬 연결하기

크루스칼 알고리즘

• 그래프 + 우선순위 큐를 복합한 탐색 알고리즘
• 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용된다.
• 그리디 알고리즘의 일종이다.

섬 연결하기 문제를 해석하기

[1] 2차원 배열이 주어지고 배열의 0번째는 현재 노드, 1번째는 현재노드와 연결할 수 있는 노드, 2번째는 현재노드와 연결할 노드의 간선을 만들기 위한 비용이다.

[2] 모든 노드가 연결되어야 한다.

[3] 연결은 한 번만 한다.
▶▶ A -> B 가 되었으면 B -> A는 할 수 없다.

[4] 노드의 순서는 상관없다.
▶▶ 1 -> 3으로 연결할 수 도 있고 3 -> 1로 연결할 수도 있다. 단 한 번만 연결하면 된다.

자바스크립트에서 크루스칼 알고리즘 사용하는 방법

[1] 그래프 간선과 비용을 2차원 배열로 만든다.

// 예시
let answer = 0;
const islands = [[0, 1, 1],[0, 2, 2],[1, 2, 5],[1, 3, 1],[2, 3, 8]];

const graph = Array.from({islands.length}, () => []);

// 순서가 상관없는 그래프이므로 a, b 양방향으로 넣어준다.
for(const [a, b, cost] of islands) {
	graph[a].push({node: b, cost});
  	graph[b].push({node: a, cost});
}

[2] 노드 수만큼의 체크배열을 만든다.
▶▶ 이는 해당 노드에 간선이 채워졌는지를 확인하기 위함이다.
간선이 만들어졌는데 중복된 간선이 만들어지지 않게 노드를 확인하기 위한 배열이 필요하다.

// 초기 값이 0인 섬의 갯수만큼의 배열
const check = Array.from({length:islands.length}, ()=>0);

[3] 큐 배열을 생성한다.

const queue = [];

[4] 루트노드의 초기 값을 넣어준 후 큐를 정렬한다.

check[0] = 1;
for(const {node, cost} of graph[0]) {
	queue.push({node, cost})
};
queue.sort((a, b) => a.cost - b.cost);

[5] while문을 이용하여 queue에 아무 것도 존재하지 않을 때까지 반복한다.
[5-1] 가장 적은 비용이 가장 앞에 있기때문에 shift하고 체크배열을 true 혹은 1로 표시하고 이미 방문한 노드이면 건너뛴다.

[5-2] 적은 비용의 간선에 해당되는 노드로 이동하여 다음 간선들을 push하고 오름차순 정렬한다.
▶▶ 이를 체크배열이 모두 1 혹은 true / queue의 모든 간선이 없어질 때까지 반복할 수 있다.
또한 간선이 생길 때마다 비용을 answer에 추가하여 최종 비용이 반환될 수 있게 누적해준다.

while(queue.length > 0) {
	const {node, cost} = queue.shift();
  	if(check[node]===1) continue;
  	answer += cost;
  	chcek[node] = 1;
  	
  	for(const {node: nextNode, cost: nextCost} of graph[node]) {
    	if(check[node] === 0) {
        	queue.push({node: nextNode, cost: nextCost});
          queue.sort((a, b) => a.cost - b.cost);
        }
    }
}

아래는 알고리즘이 실행되는 로직을 도식화한 gif이다.