← 22주차 · 유니온 파인드와 MST
보통유니온 파인드MST정렬

크루스칼 MST

정점 개수 n과 무방향 가중 간선 목록 edges가 주어져요. 각 원소 [a, b, cost]는 a와 b를 비용 cost로 잇는 간선이에요. 모든 정점을 잇는 데 드는 최소 비용을 반환해요. 다 이을 수 없으면 -1을 반환해요.

간선을 비용이 싼 순서로 정렬하고 하나씩 봐요. 두 끝점이 아직 다른 무리면 그 간선을 쓰고 무리를 합쳐요. 이미 같은 무리면 그 간선은 사이클을 만드니 건너뛰어요.

간선 n-1개를 쓰면 모든 정점이 하나로 이어진 거예요. 그 전에 쓸 간선이 떨어지면 그래프가 나뉘어 있다는 뜻이라 -1이에요.

예시

예시 1
입력
n = 4, edges = [[0, 1, 1], [1, 2, 2], [2, 3, 3], [0, 3, 4], [0, 2, 5]]
출력
6
설명
비용 1·2·3 간선을 고르면 모든 정점을 잇고 합이 6이에요.
예시 2
입력
n = 3, edges = [[0, 1, 1]]
출력
-1
설명
2번 정점을 이을 간선이 없어요.

제한 사항

  • 1 ≤ n ≤ 100,000
  • 0 ≤ edges.length ≤ 300,000
  • 0 ≤ a, b < n, 1 ≤ cost ≤ 1,000,000
parent와 크기 배열로 유니온 파인드를 만들어요. 간선을 비용 오름차순으로 정렬하고, union이 성공(두 무리를 실제로 합침)할 때만 비용을 더하고 쓴 간선 수를 세요. 쓴 간선이 n-1개가 되면 합을, 못 채우면 -1을 반환해요.
javascript
function kruskalMst(n, edges) {
  const parent = Array.from({ length: n }, (_, i) => i);
  const size = new Array(n).fill(1);
  function find(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }
  function union(a, b) {
    let ra = find(a);
    let rb = find(b);
    if (ra === rb) return false;
    if (size[ra] < size[rb]) [ra, rb] = [rb, ra];
    parent[rb] = ra;
    size[ra] += size[rb];
    return true;
  }
  const sorted = [...edges].sort((a, b) => a[2] - b[2]);
  let total = 0;
  let used = 0;
  for (const [a, b, cost] of sorted) {
    if (union(a, b)) {
      total += cost;
      if (++used === n - 1) break;
    }
  }
  return used === n - 1 ? total : -1;
}
이전 문제그래프 사이클 판정
다음 문제도시 연결하기 (프림)
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.