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

---

문제 링크: https://leetcode.com/problems/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] = [$x_i, y_i$].

The cost of connecting two points [$x_i, y_i$] and [$x_j, y_j$] is the manhattan distance between them: |$x_i - x_j$| + |$y_i - y_j$|, 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.

---

조건

• 1 <= points.length <= 1000
• $-10^6$ <= $x_i, y_i$ <= 106
• All pairs ($x_i, y_i$) are distinct.

---

내 풀이

Prims 알고리즘을 사용한다.

Prims 알고리즘은 간략히 말하면 현재 노드에서 인접한 노드 중 가장 그 거리가 짧은 것을 계속 합쳐가는 것이다.

 

주어진 points들 사이의 거리를 저장해놓고, 그래프로 나타내서 adj에 저장한다.

그 후에 모든 점을 방문하며, 방문했던 점은 visited에 저장해서 중복을 막는다.

heappop을 사용하면 현재 노드에서 인접한 노드까지의 거리 중 가장 짧은 거리를 pop해준다.

---

코드

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        N = len(points)
        adj = {i:[] for i in range(N)}
        
        for i in range(N):
            x1, y1 = points[i]
            
            for j in range(i+1, N):
                x2, y2 = points[j]
                dist = abs(x1-x2) + abs(y1-y2)
                
                adj[i].append((dist, j))
                adj[j].append((dist, i))
                
        ans = 0
        visited = set()
        cost_idx = [(0, 0)]
        
        while len(visited) < N:
            cost, idx = heappop(cost_idx)
            if idx in visited:
                continue
                
            visited.add(idx)
            ans += cost
            
            for nei in adj[idx]:
                if nei[1] not in visited:
                    heappush(cost_idx, nei)
                    
        return ans