최소 신장 트리Kruskal's 크루스칼 (Minimum spanning Tree)

edges.sort()

✅ 최소 신장 트리 (Minimum Spanning Tree, MST)란?

• 모든 노드가 연결되어 있어야 함
• 사이클이 없어야 함
• 가중치의 합이 최소가 되어야 함
• 노드가 n개일 경우, n-1개의 간선으로 이루어짐

---

🌲 크루스칼 Kruskal's Algorithm이란?

"모든 간선을 가중치 순으로 정렬해서, 비용이 가장 작은 것부터 연결해나가는 방식"

• 단, 사이클이 생기지 않도록 연결해야 하므로 Union-Find 자료구조를 이용해 cycle을 검사합니다.

---

🧠 핵심 개념 (설명에 반영할 내용)

🔹 1. 간선 수는 n-1개면 충분하다

✔️ 맞습니다. 노드가 n개면 MST는 항상 n-1개의 간선을 갖게 됩니다.

🔹 2. 어디서 출발할지는 상관 없다 (Prim과 달리)

✔️ 정확해요! Kruskal은 간선을 중심으로 정렬하여 구성하기 때문에, 시작 노드를 정할 필요가 없습니다.

🔹 3. Union-Find로 사이클 체크

✔️ 네, 사이클을 방지하기 위해 사용하는 대표적인 자료구조입니다.

---

🧩 전체 로직 요약 (크루스칼 알고리즘)

1. 모든 간선들을 [weight, u, v] 형태로 모아서 정렬 (heap 써도 OK)

edges.sort(key=lambda x: x[0])

2. Union-Find 초기화

각 노드를 자기 자신이 부모인 집합으로 시작

parent = [i for i in range(n)]
rank = [0] * n  # 선택 (union-by-rank)

3. 가장 작은 간선부터 연결 시도

for weight, u, v in edges:
    if find(u) != find(v):
        union(u, v)
        mst.append((u, v))
        total_cost += weight

• find(u) == find(v)이면 → 사이클 생기니까 제외
• 아니면 → 연결해서 MST에 포함

4. MST가 완성되면 종료 (간선 수가 n-1일 때)

---

❌ 질문에 있는 약간의 오해 정정

n1 과 n2 가 공통조산이 아니면 넘어가고, 공통조상이면, mst에 추가

→ 이건 반대로 되어 있어요!

• 공통조상(X) → 사이클이 없다 → MST에 추가해야 함
• 공통조상(O) → 사이클 생김 → 건너뛰어야 함

👉 정확한 표현:

"두 노드가 같은 집합에 속하지 않으면 연결하고, 그렇지 않으면 무시한다"

---

📌 정리: 크루스칼 핵심 요약 (최종 설명)

• 간선을 가중치 기준으로 정렬한다.
• 가장 작은 간선부터 하나씩 꺼내면서:
  • 두 노드가 같은 집합이 아니면 → MST에 추가 + Union
  • 같은 집합이면 → 사이클 생기므로 건너뜀
• 간선이 n-1개 되면 종료
• Union-Find를 통해 사이클 여부 판단

# Union Find (Disjoint Set) 자료구조 정의
class UnionFind:
    def __init__(self, n: int):
        self.parent = [i for i in range(n)]  # 각 노드의 부모를 자기 자신으로 초기화
        self.size = [1] * n  # 각 집합의 크기 (Union by size를 위함)

    def find(self, x: int) -> int:
        # x의 루트(대표 노드)를 찾음 (경로 압축 적용)
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])  # 경로 압축 (Path Compression)
        return self.parent[x]
    
    def union(self, x: int, y: int) -> bool:
        # x와 y를 같은 집합으로 연결
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x != root_y:
            # 작은 트리를 큰 트리에 붙임 (Union by size)
            if self.size[root_x] < self.size[root_y]:
                self.parent[root_x] = root_y
                self.size[root_y] += self.size[root_x]
            else:
                self.parent[root_y] = root_x
                self.size[root_x] += self.size[root_y]
            return True  # union 성공
        return False  # 이미 같은 집합이라 union 안 함

# 최소 신장 트리를 Kruskal 알고리즘으로 구현
class Solution:
    def minimumSpanningTree(self, n: int, edges: List[List[int]]) -> int:
        # 1. 간선들을 최소 힙(minHeap)에 넣기 (weight 기준 정렬)
        minHeap = []
        for n1, n2, weight in edges:
            heapq.heappush(minHeap, [weight, n1, n2])

        # 2. 유니온 파인드 초기화
        unionFind = UnionFind(n)
        minCost = 0           # 최종 MST의 가중치 총합
        
        
        """
        # 현재 연결된 컴포넌트 수 (초기엔 각 노드가 따로 떨어짐)
        # 초기에는 연결된것이 없으므로, n개의 컴퍼넌트가 있는것임.
        """
        components = n   

        # 3. MST 구성: 최소 간선부터 하나씩 연결
        """
        # components ==1 이라함은, 모두가 연결되서 1개가 됬다는 의미: loop 종료 조건
        """
        while components > 1 and minHeap: 
            weight, n1, n2 = heapq.heappop(minHeap)
            
            """
            # True 이면, 공통조상이 아니었어서, union 함수에서 연결함, 즉, 간선 추가함
            """
            if unionFind.union(n1, n2): 
                minCost += weight       # 간선을 추가했으므로 가중치 더함
                components -= 1     # 두 컴포넌트를 연결했으므로 개수 감소

        # 4. 연결 안 된 노드가 있으면 MST를 만들 수 없음
        return minCost if components == 1 else -1

 

📌 요약 흐름

단계	설명
간선 정렬	최소 가중치부터 처리하기 위해 힙 사용
Union-Find	사이클 방지 및 컴포넌트 연결 확인
MST 종료 조건	components == 1 즉, 모든 노드가 하나의 트리로 연결될 때
실패 조건	연결되지 않은 그래프면 -1 반환

---

✅ 보완 팁 (선택 사항)

• minHeap 대신 그냥 정렬로 처리해도 됨:그 다음에 순서대로 iterate하면 heapq 없이도 충분함.