[JS] 섬 연결하기

문제

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

프로그래머스

 

해당 문제는 크루스칼 알고리즘을 이용해 최단 신장 트리를 구하며 풀이하는 문제이다.

크루스칼 알고리즘을 이 문제를 통해 처음 알게되었는데, BFS 그래프 탐색인데 cost를 오름차순으로 정렬해 부모를 비교해 처리하는 알고리즘이라 생각한다.

 

코드

const find = (parent, x) => {
  if (parent[x] === x) {
    return x;
  }
  return parent[x] = find(parent, parent[x]);
}

const isSameParent = (parent, a, b) => {
  a = find(parent, a);
  b = find(parent, b);
    
  return a === b;
}

const union = (parent, st, ed) => {
  const a = find(parent, st);
  const b = find(parent, ed);
  if (a > b) {
    parent[a] = b;
  }
  else {
    parent[b] = a;
  }
}

const solution = (n, costs) => {
  let answer = 0;
  const arr = Array.from({ length: n }, (_, i) => i);
  costs.sort((a, b) => a[2] - b[2]);
    
  for (const [a, b, cost] of costs) {
    if (!isSameParent(arr, a, b)) {
      answer += cost;
      union(arr, a, b);
    }
  }
  return answer;
}