[ 프로그래머스_Lv3 ] 섬 연결하기 ( 크루스칼 - 자바스크립트 )

문제

https://programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

 

How to Solve ?

 

[1] 문제에 들어 가기 전에

 

이 문제를 풀기 위해서는 최소 스패닝(=신장) 트리를 해결 하기 위한  [ 크루스칼 / 프림 ] 알고리즘을 이해 하신 후에 풀 수 있는 문제라고 생각합니다.

 

1-1 ) 크루스칼 

크루스칼은 '선'을 기준으로 최소 신장 트리를 찾는 알고리즘으로써, 선의 길이를 오름차순으로 정렬 한뒤 아래의 그림과 같이 순서대로 선을 연결 합니다.

 

다음과 같이 선을 연결하며, 찾을 때 발생 할 수 있는 문제는 "사이클이 생긴다" 라는 것인데, 사이클이 생기면 사이클 내부를 계속 돌며 값이 끊임없이 증가하거나 혹은 다른 모든 노드와 연결이 불 가능 해지기 때문에 이를 방지 할 수 있는 장치를 두어야 합니다.

 

이를 방지 할 수 있는 방법은 다양 하지만 일반적으로는 1) DFS 를 통해 노드를 탐색하는 방법을 채택하거나 2) union-find 라는 기법을 사용하여 연결 하고자 하는 노드의 부모가 같은지 확인하여 사이클의 유무를 확인 합니다.

 

 

 

 

1-2) 프림

 

프림 알고리즘은 "정점(=vertex)" 를 중심으로 최소 신장 트리를 찾는다는 점에서 크루스칼과 다릅니다.

 

프림은 임의의 간선은 선택하고, 선택한 간선의 정점으로부터 가장 낮은 가중치를 얻을 수 있는 정점을 n-1개의 간선이 연결 될 때까지 반복하여 문제를 해결 할 수 있습니다.

 

전체 코드

 

// default 상태에서의 부모는 자기 자신이다.
// 만약 자기 자신이 아니라면, 다른 노드와 연결 된 것 임으로
// 그 값을 찾아서 반환 해주어야 한다.
const find = (parent, x) => {
  if (parent[x] !== x) {
    parent[x] = find(parent, parent[x]);
  }
  return parent[x];
};
 
 
// 값이 더 작다는 것은, 선행된 노드이기에 
// 선행된 노드에 간선을 연결 해주는 것이 옳다.
const union = (parent, a, b) => {
  a = find(parent, a);
  b = find(parent, b);
 
  return a > b ? (parent[a] = b) : (parent[b] = a);
};
 
function solve(n, costs) {
  // [0,1,2,3]
  // 정점을 0부터 시작했으면 [0,1,2] 로 구성해도 무관
  const parent = Array.from({ length: n + 1 }, (v, i) => i);
  // 간선의 값을 오름차순으로 정렬
  costs.sort((a, b) => a[2] - b[2]);
 
  let sum_cost = 0;
 
  costs.forEach((cost) => {
    // 부모가 다르다는건, 사이클이 없다는 것을 의미.
    if (find(parent, cost[0]) !== find(parent, cost[1])) {
      union(parent, cost[0], cost[1]);
      console.log(parent);
      sum_cost += cost[2];
    }
  });
  return sum_cost;
}
 
const [vertex, edge] = [3, 3];
 
const costs = [
  [1, 2, 1],
  [2, 3, 2],
  [1, 3, 3],
];
 
console.log(solve(vertex, costs));