HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
👻
개발 기록/
코딩테스트 스터디
코딩테스트 스터디/
Min Cost to Connect All Points

Min Cost to Connect All Points

Link
https://leetcode.com/problems/min-cost-to-connect-all-points/
Deadline
Aug 21, 2022
Status
Archived
Type
Array
union-find

문제

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].
The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.
Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.
notion image
Example 2:
Constraints:
  • 1 <= points.length <= 1000
  • 106 <= xi, yi <= 106
  • All pairs (xi, yi) are distinct.
 

풀이

재영
효성
Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18

/**
 * @param {number[][]} points
 * @return {number}
 */
class MinHeap {
  constructor() {
    this.heap = [null];
    this.size = 0;
  }

  heappush(value) {
    this.heap.push(value);
    let nowIndex = this.heap.length - 1;
    let parentIndex = Math.floor(nowIndex / 2);
    while (nowIndex > 1 && this.heap[parentIndex][2] > this.heap[nowIndex][2]) {
      this.swap(nowIndex, parentIndex);
      nowIndex = parentIndex;
      parentIndex = Math.floor(nowIndex / 2);
    }
    this.size += 1;
  }

  heappop() {
    const returnValue = this.heap[1];
    this.heap[1] = this.heap.pop();

    let nowIndex = 1;
    let leftIndex = nowIndex * 2;
    let rightIndex = nowIndex * 2 + 1;

    if (!this.heap[rightIndex]) {
      if (
        this.heap[leftIndex] &&
        this.heap[nowIndex][2] > this.heap[leftIndex][2]
      ) {
        this.swap(nowIndex, leftIndex);
        return returnValue;
      }
    }

    while (
      this.heap[rightIndex] &&
      (this.heap[nowIndex][2] > this.heap[leftIndex][2] ||
        this.heap[nowIndex][2] > this.heap[rightIndex][2])
    ) {
      if (this.heap[leftIndex][2] < this.heap[rightIndex][2]) {
        this.swap(nowIndex, leftIndex);
        nowIndex = leftIndex;
      } else {
        this.swap(nowIndex, rightIndex);
        nowIndex = rightIndex;
      }

      leftIndex = nowIndex * 2;
      rightIndex = nowIndex * 2 + 1;
    }
    this.size -= 1;
    return returnValue;
  }
    
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
}

const calcDist = (x1, y1, x2, y2) => {
  return Math.abs(x1 - x2) + Math.abs(y1 - y2);
};

const findParent = (x, parent) => {
  return parent[x] === x ? x : findParent(parent[x], parent);
};

const unionFind = (a, b, parent) => {
  const parentA = findParent(a, parent);
  const parentB = findParent(b, parent);

  if (parentA <= parentB) {
    parent[parentB] = parentA;
  } else {
    parent[parentA] = parentB;
  }
};

const minCostConnectPoints = (points) => {
  let total = 0;
  let cnt = 0;

  const minHeap = new MinHeap();

  for (let i = 0; i < points.length; i += 1) {
    const [x1, y1] = points[i];

    for (let j = i + 1; j < points.length; j += 1) {
      const [x2, y2] = points[j];

      minHeap.heappush([i, j, calcDist(x1, y1, x2, y2)]);
    }
  }

  const parent = Array.from({ length: points.length + 1 }, (_, idx) => idx);
    
  while (minHeap.size) {
    const [from, to, cost] = minHeap.heappop();

    if (findParent(from, parent) !== findParent(to, parent)) {
      unionFind(from, to, parent);
      total += cost;
      cnt += 1;

      if (cnt === points.length) break;
    }
  }

  return total;
};
var minCostConnectPoints = function(points) {
    const len = points.length;
    const dist = [];
    const graph = [...Array(len)].map((_, i) => i);
    let totalDist = 0;
    
    const find = (id) => {
        if(graph[id] === id) return id;
        graph[id] = find(graph[id]);
        return graph[id];
    }
    
    for(let i = 0; i < len; i++) {
        for(let j = i + 1; j < len; j++) {
            const [xi, yi] = points[i];
            const [xj, yj] = points[j];
            const distance = Math.abs(xi - xj) + Math.abs(yi - yj);
            dist.push([i, j, distance]);
        }
    }
    
    dist.sort((a, b) => a[2] - b[2]);
    
    for(let [x, y, d] of dist) {
        const rootX = find(x);
        const rootY = find(y);
        if(rootX === rootY) continue;
        graph[rootY] = rootX;
        totalDist += d;
    }
    
    return totalDist;
};