[1584] Min Cost to Connect All Points | LeetCode Medium

🔎 문제설명

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

cost 값을 보면 알겠지만, 점과 점 사이의 공식이 아니라는 것을 알 수 있다.

모든 점이 맨해튼 거리공식으로 이어졌을 때 가장 짧은 길이를 반환하는 게 문제이다.

Example 2

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

제한사항

• 1 ≤ points.length ≤ 1000
• $-10^6 ≤ xi, yi ≤ 10^6$
• All pairs (xi, yi) are distinct.

---

🚩 접근법

이 문제의 접근법은 그래프의 모든 점들을 연결해서 연결된 모든 점들 사이의 맨하튼거리의 합이 최소값이 되도록 해야합니다.

이것은 최소 스패닝 트리(MST)의 총 가중치를 찾는 것과 같습니다.

최소 스패닝 트리를 알아보자면,

먼저 트리란 사이클을 갖지 않는 그래프입니다.

스패닝 트리는 가중치를 갖는 트리입니다.

최소 스패닝(신장)트리는 각각의 간선들이 갖는 가중치가 최소가 되는 트리를 말합니다.

최소 스패닝을 구하는 유명한 방법은 크루스칼과 프림 알고리즘이 있습니다.

---

🧊 파이썬 코드

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        d, res = {(x, y): float('inf') if i else 0 for i, (x, y) in enumerate(points)}, 0
        while d:
            x, y = min(d, key=d.get)  
            res += d.pop((x, y))      
            for x1, y1 in d:          
                d[(x1, y1)] = min(d[(x1, y1)], abs(x-x1)+abs(y-y1))
        return res