[Javascript/자바스크립트] (프로그래머스) 섬 연결하기

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

코드

function solution(n, costs) {
  let answer = 0;
  const parent = [];
  for (let i = 0; i < n; i++) {
    parent.push(i);
  }

  const findParent = (x) => {
    if (x !== parent[x]) {
      parent[x] = findParent(parent[x]);
    }
    return parent[x];
  };

  const union = (a, b) => {
    const aParent = findParent(a);
    const bParent = findParent(b);

    if (aParent === bParent) return false;

    if (aParent < bParent) {
      parent[bParent] = aParent;
    } else {
      parent[aParent] = bParent;
    }

    return true;
  };

  costs.sort((a, b) => a[2] - b[2]);
  let connected = 0;
  for (const [s, e, cost] of costs) {
    if (union(s, e)) {
      connected++;
      answer += cost;
    }
    if (connected === n - 1) break;
  }
  return answer;
}

 

모든 섬을 잇는 최소 비용을 구하는 문제였기에 최소 신장 트리(MST)를 만들기 위한 알고리즘인 크루스칼을 사용했다.

 

크루스칼 알고리즘은 다음과 같은 단계로 진행된다.

1. 간선들을 가중치 오름차순으로 정렬한다.

2. 가중치가 작은 간선부터 살펴보는데, 사이클을 생성하지 않는 간선이라면 트리에 포함시키고, 사이클을 생성한다면 포함하지 않는다.

3. 이 과정은 n-1개의 간선이 선택될 때까지 수행한다. 왜냐하면 n개의 노드가 있는 MST에는 간선이 n-1개이어야 하기 때문이다.