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

문제 출처

Lv.3 섬 연결하기- JavaScript

https://school.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

정답

class UnionFind {
  constructor(size) {
  // 각 노드의 부모 노드를 저장하는 배열입니다. 초기화 시 각 노드가 자기 자신을 부모로 갖도록 설정됩니다.
    this.parent = Array.from({ length: size }, (_, idx) => idx);
  // 각 노드의 깊이(또는 높이)를 저장하는 배열입니다. 초기화 시 [0,0,0,0]
    this.rank = Array.from({ length: size }, () => 0);
  }

// 특정 노드의 최상위 부모 노드(루트 노드)를 찾는 함수입니다. 
  find(v) {
    if (this.parent[v] !== v) {
      this.parent[v] = this.find(this.parent[v]);
    }
    return this.parent[v];
  }

// 두 노드를 연결하는 함수입니다. 두 노드의 루트 노드를 찾아서 합치는 작업을 수행합니다.
  union(v1, v2) {
    const root1 = this.find(v1);
    const root2 = this.find(v2);

    if (root1 === root2) return false;

// 만약 두 노드의 루트 노드의 깊이가 다르다면, 깊이가 낮은 트리를 깊이가 높은 트리의 하위에 연결합니다.
    if (this.rank[root1] > this.rank[root2]) {
      this.parent[root2] = root1;
    } else {
    // 깊이가 동일한 두 트리를 연결할 경우, 한 트리의 깊이를 1 증가시키고 다른 트리를 그 하위에 연결합니다.
      this.parent[root1] = root2;
      if (this.rank[root1] === this.rank[root2]) {
        this.rank[root2]++;
      }
    }

    return true;
  }
}

function solution(n, costs) {
    costs.sort((a, b) => a[2] - b[2]);

    const uf = new UnionFind(n);
    let totalCost = 0;

    for (const [from, to, weight] of costs) {
      if (uf.union(from, to)) {
        totalCost += weight;
      }
    }

    return totalCost;
}