Today's Challenge

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

Min Cost to Connect All Points - LeetCode

최소 스패닝 트리를 구하는 문제다.

파이썬으로는 코드를 매우 간단하게 표시 가능한데, 가독성이 별로라는 난 좀 풀어서 썼다.

모든 점의 거리를 일단 무한대 값으로 놓고
하나의 점으로부터 나머지 점들의 거리를 모두 구해서 가장 작은 값을 저장해서 합계를 내는 방식이다.

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        d = {}
        res = 0
        for i, (x, y) in enumerate(points):
            if i:
                d[(x, y)] = float('inf')
            else:
                d[(x, y)] = 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