프로그래머스 LEVEL 3(섬 연결하기)

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2022-12-23

  • 해결 방법 :

    • 크루스칼 알고리즘을 통해 문제 해결
      • 각 노드 별 조상(parent)를 저장할 배열 nodes 자기 자신으로 초기화
      • 입력받은 costs 배열 가중치에 따라 오름차순 정렬
      • costs를 돌며
        • from에서 to까지 연결할 경우 부모가 같으면 사이클이 생성되므로 부모가 같지 않은 경우에만 연결(find)
        • 부모가 같지 않은 경우,
          • 연결해도 되므로 answer에 cost 추가
          • 두 노드의 부모 중 작은 값으로 부모 합치기
          • 이 때 모든 node의 부모가 같은 경우(set의 size가 1) break

  • 회고 :

    • 처음에 dp를 활용해 문제를 해결할 수 있을거라고 생각해 dp로 접근해봤는데 더 간단한 크루스칼 알고리즘이 존재했다.

  • 코드

    function solution(n, costs) {
  let answer = 0;
  const nodes = Array.from({ length: n }, (_, i) => i);
  costs.sort((a, b) => a[2] - b[2]);

  const getParent = (n) => {
    if (nodes[n] === n) return n;
    return (nodes[n] = getParent(nodes[n]));
  };

  const find = (from, to) => getParent(from) === getParent(to);

  const union = (from, to) => {
    const fromNodeParent = getParent(from),
      toNodeParent = getParent(to);
    fromNodeParent > toNodeParent
      ? (nodes[fromNodeParent] = toNodeParent)
      : (nodes[toNodeParent] = fromNodeParent);
  };

  for (const [from, to, cost] of costs) {
    if (!find(from, to)) {
      answer += cost;
      union(from, to);
      if (new Set(nodes).size === 1) break;
    }
  }

  return answer;
}

  • 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges