[프로그래머스] 섬 연결하기 - JavaScript

프로그래머스 Level 3 - 섬 연결하기

• 문제 분류 : 탐욕법(Greedy)
• 문제 출처 : 프로그래머스 Level 3 - 섬 연결하기

📌 문제 설명

📌 생각한 풀이 방법 (Kruskal 알고리즘)

1. 해당 섬들의 parent를 저장하는 배열을 생성함
2. 모든 섬의 다리 건설 비용의 오름차순으로 정렬함
3. 해당 경로를 parent를 기반으로 Union, Find 알고리즘을 활용하여 경로를 찾음

📌 풀이

function getParent(parentArr, point) {
  // 특정 섬의 parent를 반환함
  if (parentArr[point] === point) return point;
  return (parentArr[point] = getParent(parentArr, parentArr[point]));
}

function setParent(parentArr, a, b) {
  // 해당 섬의 parent를 설정함
  const parentA = getParent(parentArr, a);
  const parentB = getParent(parentArr, b);
  if (parentA < parentB) return (parentArr[parentB] = parentA);
  return (parentArr[parentA] = parentB);
}

function solution(n, costs) {
  let answer = 0;

  // 해당 섬들의 parent를 저장하는 배열을 생성함
  let parentArr = Array(n)
    .fill()
    .map((obj, index) => index);

  // 모든 섬의 다리 건설 비용의 오름차순으로 정렬
  costs.sort((a, b) => {
    if (a[2] === b[2]) return a[0] - b[0];
    return a[2] - b[2];
  });

  // 해당 경로를 Union, Find 알고리즘을 활용하여 경로를 찾음
  for (const cost of costs) {
    if (getParent(parentArr, cost[0]) !== getParent(parentArr, cost[1])) {
      answer += cost[2];
      setParent(parentArr, cost[0], cost[1]);
    }
  }

  return answer;
}