[PS/Python] 섬 연결하기 / Greedy / Kruskal / Union-Find / Prim

https://school.programmers.co.kr/learn/courses/30/lessons/42861

 

섬 연결하기 문제의 경우,

 

• n개의 섬이 있고, costs에 [섬1, 섬2, 비용] 형태로 연결 비용이 주어짐.
• 모든 섬을 최소 비용으로 연결하는 방법을 찾아야 함.
• MST(최소 신장 트리, Minimum Spanning Tree) 알고리즘(Kruskal or Prim)으로 해결함
• 최소 비용으로 연결해야 하므로 사이클이 생겨서는 안됨

📌 사이클이 형성되면 안 되는 이유 (MST에서)

➡ MST(최소 신장 트리, Minimum Spanning Tree)는 "모든 노드를 연결하면서도, 사이클이 없는 트리"여야 함.
➡ 즉, 같은 노드를 두 번 방문하는 "순환 경로(사이클)"가 있으면 트리가 아님!

---

1. MST(최소 신장 트리, Minimum Spanning Tree)의 정의

• 모든 노드를 포함하는 "연결 그래프"
• 사이클이 없는 그래프
• 간선의 가중치 합이 최소

즉, 사이클이 포함되면 MST가 될 수 없음! 🚫

---

2. 사이클이 생기면 최소 신장 트리가 깨지는 이유

(1) 사이클이 있으면 불필요한 간선이 추가됨

• 예를 들어, A → B → C → A 처럼 돌아오는 길이 존재하면,
  어떤 노드는 최소 비용으로 연결되지 않음.
• 즉, MST는 가장 적은 간선으로 모든 노드를 연결하는 것이 목표인데,
  사이클이 생기면 "쓸데없는 간선"이 추가되면서 비용이 증가함.

(2) MST는 항상 "n-1개의 간선"을 가져야 함

• MST는 "노드 개수 - 1"개의 간선만 존재해야 함.
• 사이클이 발생하면 n개 이상의 간선이 추가되므로 MST의 조건을 위반함.

따라서 사이클 방지를 위해,

 

Union-Find

💡 MST에서 사이클을 방지하려면, Kruskal 알고리즘에서 "Union-Find"를 활용해야 함.

• Union-Find를 사용하면 "두 노드가 이미 같은 집합(연결된 상태)인지 확인"할 수 있음.
• 만약 두 노드가 이미 같은 집합이면(즉, 이미 연결된 상태) → 이 간선을 추가하면 사이클이 됨 → 추가하지 않음.

✔ 사이클 방지 코드 (Union-Find)

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # 경로 압축 (Path Compression)
    return parent[x]

def union(parent, rank, a, b):
    rootA = find(parent, a)
    rootB = find(parent, b)
    
    if rootA != rootB:  # 두 노드가 다른 집합이면 합침
        if rank[rootA] > rank[rootB]:
            parent[rootB] = rootA
        elif rank[rootA] < rank[rootB]:
            parent[rootA] = rootB
        else:
            parent[rootB] = rootA
            rank[rootA] += 1

 

#최소 신장 트리(MTS) 그래프의 모든 정점을 연결하는 트리 중에서 간선 가중치의 합
#이 최소인 트리

#최소 연결 비용으로 모든 섬(노드)이 서로 통행 가능하도록 만들 때 

def solution(n,costs):
    
    #cost 현재 다리를 건설하는 비용을 의미함
    #비용을 기준으로 간선을 오름차순 정렬함
    costs.sort(key=lambda x: x[2])
    
    #각 섬의 부모 노드를 저장함
    parent = [i for i in range(n)]
    
    #루트 노드를 찾는 함수
    def find(node):
        if parent[node] != node:
            parent[node] = find(parent[node]) # 재귀함수
        return parent[node]
    
    # 두 노드를 합치는 함수
    #초기 상태에서는 모든 노드가 자기 자신으로 가짐
    #루트(집합을 대표하는 노드)가 다르면, 하나의 루트로 통일하여 연결함
    def union(node1,node2):
        
        root1 = find(node1)
        root2 = find(node2)
        
        if root1 != root2:
            parent[root2] = root1
    
    #최소 비용 계산
    answer = 0
    for node1 , node2 , cost in costs:
        if find(node1) != find(node2): # 두 노드가 다른 집합에 속해 있으면
            union(node1,node2) # 두 노드를 연결
            answer += cost # 비용을 추가함
    return answer

#print(solution(4,[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]))

 

 

다른 풀이 (Kruskal 알고리즘)

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # 경로 압축(Path Compression)
    return parent[x]

def union(parent, rank, a, b):
    rootA = find(parent, a)
    rootB = find(parent, b)
    
    if rootA != rootB:  # 두 노드가 다른 집합이면 합침
        if rank[rootA] > rank[rootB]:
            parent[rootB] = rootA
        elif rank[rootA] < rank[rootB]:
            parent[rootA] = rootB
        else:
            parent[rootB] = rootA
            rank[rootA] += 1

def solution(n, costs):
    costs.sort(key=lambda x: x[2])  # 1. 간선을 가중치 기준으로 정렬
    parent = list(range(n))  # Union-Find 부모 테이블 초기화
    rank = [0] * n  # Union-Find 랭크 초기화
    
    min_cost = 0
    edges_used = 0  # 사용된 간선 개수 (MST는 n-1개의 간선이 필요)
    
    for a, b, cost in costs:
        if find(parent, a) != find(parent, b):  # 2. 사이클이 발생하지 않는 경우에만 선택
            union(parent, rank, a, b)  # 3. 두 노드를 같은 집합으로 합침
            min_cost += cost
            edges_used += 1
            if edges_used == n - 1:  # MST가 완성되면 종료 (간선 개수: n-1)
                break
    
    return min_cost

🔍 개선된 코드의 핵심 로직

✅ 1. Kruskal 알고리즘 적용

• 간선을 오름차순으로 정렬하여 가장 작은 가중치를 먼저 선택.
• 사이클이 생기지 않는 간선만 추가하여 최소 신장 트리(MST)를 구성.

✅ 2. Union-Find 활용 (서로소 집합)

• find(parent, x): 특정 노드 x가 속한 집합의 루트를 찾음 (경로 압축 최적화 포함).
• union(parent, rank, a, b): 두 노드 a, b가 속한 집합을 합침.

✅ 3. 최적의 최소 비용 그래프 구성

• MST의 간선 개수는 n-1개가 되어야 하므로, edges_used == n-1이면 조기 종료.

---

🚀 시간 복잡도 분석

• 간선 정렬: O(E log E)
• Union-Find (Find & Union 연산): O(E α(N))
  • (여기서 α(N)은 거의 O(1)에 가깝다고 볼 수 있음)
• 총 시간 복잡도: O(E log E)✅ 현재 코드보다 훨씬 효율적이고 최적화된 풀이!

📌 Kruskal 알고리즘 vs Prim 알고리즘

Kruskal	간선 중심 (Edge-based)	O(E log E)	가중치 작은 간선부터 선택
Prim	정점 중심 (Vertex-based)	O(E log V)	하나의 정점에서 시작

📌 Kruskal은 "간선 개수가 적은 그래프"에서 유리
📌 Prim은 "정점 개수가 적은 그래프"에서 유리