프로그래머스 고득점 Kit 섬 연결하기 문제 풀이 JS

그레이쁘·2021년 9월 1일
0

알고리즘

목록 보기
7/11

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

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

섬의 개수 n은 1 이상 100 이하입니다.
costs의 길이는 ((n-1) * n) / 2이하입니다.
임의의 i에 대해, costs[i][0] 와 costs[i][1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i][2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

n	costs						return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

접근 방법

가중치가 적은 간선부터 채택하는 크루스칼 알고리즘으로 풀었다.
costs를 비용이 적은 순으로 정렬하고,
가장 적은 값부터 보면서 모든 정점이 하나의 부모를 가지면서 선택된 간선이 n-1개가 될 때까지 while문을 돌렸다.

코드

function solution(n, costs) {
  function union(a, b) {
    let rootA = find(a);
    let rootB = find(b);
    if (rootA === rootB) return false;
    parent[rootB] = rootA;
    return true;
  }
  function find(a) {
    if (parent[a] === a) return a;
    return (parent[a] = find(parent[a]));
  }
  costs.sort(function (a, b) {
    return a[2] - b[2];
  });
  let answer = 0,
    parent = [],
    count = 0;
  for (let i = 0; i < n; i++) parent.push(i);
  while (count < n - 1) {
    const min = costs.shift();
    if (find(min[0]) != find(min[1])) {
      union(min[0], min[1]);
      answer += min[2];
      count++;
    }
  }
  return answer;
}
profile
그냥 걷는 사람🚶‍♀️

0개의 댓글