a-094-min-cost-to-connect-all-points● today2026-08-22mediumleetcode #1584neetcode150

모든 점을 연결하는 최소 비용

#array#union-find#graph#minimum-spanning-tree#prims-algorithm#kruskals-algorithm#boruvkas-algorithm

↗ leetcode #1584 · a-094-min-cost-to-connect-all-points

문제

· problem

P.a-094-min-cost-to-connect-all-points

모든 점을 연결하는 최소 비용

2D 평면 위의 정수 좌표를 나타내는 배열 points가 주어집니다. 여기서 points[i] = [xi, yi]입니다. 두 점 [xi, yi]와 [xj, yj]를 연결하는 비용은 맨해튼 거리입니다: |xi - xj| + |yi - yj|. 여기서 |val|은 val의 절댓값입니다. 모든 점을 연결하는 최소 비용을 반환하세요. 모든 점이 연결되어 있다는 것은 임의의 두 점 사이에 정확히 하나의 단순 경로가 존재한다는 의미입니다.

제약

· 1 ≤ points.length ≤ 1000
· -1e6 ≤ xi, yi ≤ 1e6
· All pairs (xi, yi) are distinct

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[[0,0],[2,2],[3,10],[5,2],[7,0]]

example 2input → output

[[3,12],[-2,5],[-4,1]]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
모든 점이 '연결되어 있다'는 것은 정확히 무엇을 의미하나요?
☐
N개의 점을 연결하려면 정확히 몇 개의 간선이 필요한가요?
☐
맨해튼 거리가 아닌 다른 거리 메트릭(예: 유클리드)을 사용할 수 있나요?
☐
가장 가까운 두 점을 항상 먼저 연결하면 최소 비용을 보장할까요?
☐
이 문제가 최소 신장 트리(MST) 문제인 이유가 뭐예요?
☐
이 구현의 시간 복잡도가 O(n² log n)인 이유는 뭐예요?
☐
Union-Find를 사용하는 Kruskal 알고리즘이 더 효율적일까요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 그래프 크기 N 결정

○

N = len(points)

○

N = len(points) - 1

○

N = len(points) * (len(points) - 1) // 2

step 2· 모든 점 쌍의 맨해튼 거리 계산 및 간선 추가

○

dist = abs(x1 - x2) + abs(y1 - y2)

○

dist = abs(x1 - x2) * abs(y1 - y2)

○

dist = (x1 - x2) ** 2 + (y1 - y2) ** 2

step 3· Prim 알고리즘 초기화: 결과값, 방문 집합, 최소 힙

○

minH = [[0, 0]]  # [cost, point]

○

minH = [[0, i] for i in range(N)]

○

minH = []

step 4· 최소 비용 간선 추출 및 중복 확인│ 중첩

○

if i in visit:

○

if cost == 0: continue

○

# 확인 생략

step 5· 현재 간선 비용을 결과에 더하고 노드를 방문 처리│ 중첩

○

res += cost

○

res += cost * 2

○

res = cost + res

step 6· 현재 노드의 미방문 이웃들을 힙에 추가│ 중첩

○

if nei not in visit:

○

for neiCost, nei in adj[i]: heapq.heappush(minH, [neiCost, nei])

○

for neiCost, nei in adj[i]: heapq.heappush(minH, [neiCost, nei]) if nei not in minH

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def minCostConnectPoints(self, points: List[List[int]]) -> int:

        N = len(points)

        adj = {i: [] for i in range(N)}  # i : list of [cost, node]

        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])

        # Prim's

        res = 0

        visit = set()

        minH = [[0, 0]]  # [cost, point]

        while len(visit) < N:

            cost, i = heapq.heappop(minH)

            if i in visit:

                continue

            res += cost

            visit.add(i)

            for neiCost, nei in adj[i]:

                if nei not in visit:

                    heapq.heappush(minH, [neiCost, nei])

        return res

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[[0,0],[2,2],[3,10],[5,2],[7,0]]

→

case 2

[[3,12],[-2,5],[-4,1]]

→

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.