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.
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
