[프로그래머스#JS] 섬 연결하기

문제

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

풀이

최소 신장 트리(MST) 문제로 크루스칼 알고리즘 이용해서 풀었습니다.

• 최소 비용을 찾기 위해 비용 순서대로 오름차순 정렬.
• 사이클 검사
  1. 모든 정점에 대해 부모노드를 자기 자신으로 설정.
  2. 재귀함수를 이용해 정렬된 순서대로 from, to 노드의 부모노드 탐색.
  3. from, to의 부모노드가 같다면, 같은 사이클에 있다는 뜻. 다른 경우 추가.
• 부모 노드 union
  1. 추가됐다면 추가된 노드의 부모노드 설정.

코드

function solution(n, costs) {
  let answer = 0;
  costs.sort((a, b) => a[2] - b[2]);

  let parentArr = new Array(n).fill(0).map((_, idx) => idx);

  costs.forEach((_, i) => {
    const [from, to, dist] = costs[i];

    // isSameNode : 부모 노드가 같은 지 체크
    if (!isSameNode(parentArr, from, to)) {
      answer += dist;
      unionParent(parentArr, from, to);
    }
  });

  console.log(answer);
  return answer;
}

function unionParent(parentArr, a, b) {
  a = getParent(parentArr, a);
  b = getParent(parentArr, b);

  if (a < b) parentArr[b] = a;
  else parentArr[a] = b;
}

function getParent(parentArr, x) {
  if (parentArr[x] === x) return x;
  return (parentArr[x] = getParent(parentArr, parentArr[x]));
}

function isSameNode(parentArr, a, b) {
  a = getParent(parentArr, a);
  b = getParent(parentArr, b);

  if (a === b) return true;
  else return false;
}

참고

https://m.blog.naver.com/ndb796/221230994142