2023.09.15 Today's Challenge

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

Min Cost to Connect All Points - LeetCode

크루스칼 알고리즘으로 푸는 문제

def m_dist(p1, p2):
    return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        visited = [False] * n
        heap_dict = {0: 0}
        min_heap = [(0, 0)]
        mst_weight = 0

        while min_heap:
            w, u = heappop(min_heap)

            if visited[u] or heap_dict.get(u, float('inf')) < w:
                continue

            visited[u] = True
            mst_weight += w

            for v in range(n):
                if not visited[v]:
                    n_dist = m_dist(points[u], points[v])

                    if n_dist < heap_dict.get(v, float('inf')):
                        heap_dict[v] = n_dist
                        heappush(min_heap, (n_dist, v))
        
        return mst_weight