[JS] 섬 연결하기

union-find + 그리디 알고리즘을 활용해서 해결하였다.

 

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

프로그래머스

 

 

해당 문제는 그리디 알고리즘으로 해결할 수 있다. 우선 다리의 건설 비용을 오름차순으로 정렬을 해준다.

 

이후 정렬된 배열을 순회하며 두 다리가 연결이 안되어 있다면 연결해준다.

 

이 두 다리가 연결이 안되어 있는지를 확인하기 위해서 union-find 알고리즘을 활용하였다.

 

1. costs 배열을 비용을 기준으로 오름차순 정렬

2. costs배열을 순회하며 다리가 연결되어 있지 않다면 연결

3. 다리를 연결하고 만약 모든 다리가 연결되었다면 지금까지 건설 비용을 반환

 

 

 

 

//union-find
const getParent = (a, arr) => {
  if (arr[a] === a) return a;
  return (arr[a] = getParent(arr[a], arr));
};

const union = (a, b, arr) => {
  a = getParent(a, arr);
  b = getParent(b, arr);

  if (a > b) arr[a] = b;
  else arr[b] = a;
};

const isUnion = (a, b, arr) => {
  a = getParent(a, arr);
  b = getParent(b, arr);
  return a === b ? true : false;
};

//모든 섬이 연결되었는지 확인
const checkIsConnect = (arr) => {
  return arr.every((v) => v === 0);
};

function solution(n, costs) {
  //가격낮은순으로 정렬
  costs.sort((a, b) => a[2] - b[2]);
  let parents = [...Array(n)].map((_, i) => i);

  let ret = 0;
  for (const [s, e, c] of costs) {
    // 연결이 안되어있다면 연결해줌
    if (!isUnion(s, e, parents)) {
      union(s, e, parents);
      ret += c;
      //연결한 후에 모든 섬이 연결되었는지 확인
      parents = parents.map((v) => getParent(v, parents));
      if (checkIsConnect(parents)) return ret;
    }
  }
}