엔지니어 게시판
LeetCode 솔루션 분류

1584. Min Cost to Connect All Points

컨텐츠 정보

본문

[LeetCode 시즌 3] 2022년 4월 25일 문제입니다

https://leetcode.com/problems/min-cost-to-connect-all-points/


[Medium] 1584. Min Cost to Connect All Points

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.

 

Example 1:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation: 

We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.

Example 2:

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

 

Constraints:

  • 1 <= points.length <= 1000
  • -106 <= xi, yi <= 106
  • All pairs (xi, yi) are distinct.

관련자료

댓글 1

나무토끼님의 댓글

  • 익명
  • 작성일
Runtime: 7351 ms, faster than 5.00% of Python3 online submissions for Min Cost to Connect All Points.
Memory Usage: 97.8 MB, less than 31.36% of Python3 online submissions for Min Cost to Connect All Points.
class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        hpq = []
        parent = defaultdict(int)
        self.ans = 0
        
        def find(x, parent):
            if parent[x] == x:
                return x
            parent[x] = find(parent[x], parent)
            return parent[x]
        
        def union(x, y, parent, temp):
            px = find(x, parent)
            py = find(y, parent)
            if px != py:
                parent[px] = py
                return temp
            return 0
        
        for i in range(len(points)):
            parent[(points[i][0], points[i][1])] = (points[i][0], points[i][1])
            for j in range(i + 1, len(points)):
                temp = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                hpq.append([temp, i, j])
        hpq.sort()
        for i in range(len(hpq)):
            p = hpq[i]
            self.ans += union(tuple(points[p[1]]), tuple(points[p[2]]), parent, p[0])
        return self.ans
            
            
        
전체 94 / 4 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 659 명
  • 오늘 방문자 3,980 명
  • 어제 방문자 7,431 명
  • 최대 방문자 14,831 명
  • 전체 회원수 1,542 명
알림 0