[Python/Programmers] 42861. 섬 연결하기

💬 문제

문제 난이도: Lv.3

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42861

문제 설명

n개의 섬 사이에 다리를 건설하는 비용이 주어진다.
모든 섬을 연결할 때 필요한 최소 비용을 바노한하라.
다리를 여러 번 건너서라도 도달할 수만 있다면 통행 가능한 경우이다. 가령 A섬과 C섬을 잇는 다리가 없더라도 B섬을 거쳐 갈 수 있다면 A섬과 C섬은 서로 통행 가능하다.

문제조건
1. 연결할 수 없는 섬은 주어지지 않는다.
2. A섬과 B섬을 잇는 비용이 C라면, B섬과 A섬을 잇는 비용도 C이다.(무방향)
3. 섬의 개수는 1~100개이다.
3. 간선의 개수는 ((n-1) * n)/2 이하이다.

❗️접근 방법

Spanning Tree

스패닝 트리란 무방향 그래프에서 모든 노드가 연결되어 있는 트리이다.
보통 그래프는 여러 개의 스패닝 트리를 갖지만, 비연결 그래프는 스패닝 트리를 갖지 않는다.

MST(Minimum Spanning Tree)

최소 스패닝 트리는 간선의 가중치가 있는 무방향 그래프에서 사이클이 없고 모든 노드가 연결되어 있으며 간선의 가중치의 합이 최소가 되는 그래프이다.
연결그래프에서 최소 스패닝 트리는 한 개 이상이다.

Kruskal

크루스칼 알고리즘은 가중치가 있는 무방향 그래프에서 MST(최소 스패닝 트리)을 찾는 알고리즘이다.
크루스칼 알고리즘은 각 단계마다 사이클을 생성하지 않으면서 가중치가 가장 작은 간선을 추가하기 때문에 그리디 알고리즘이 사용된다.
사이클이 생성되는지는 union-find 알고리즘을 사용한다.

Disjoint Set

Disjoint Set이란 서로 동통된 원소를 가지고 있지 않는 두 개 이상의 집합.
Disjoint Set 자료구조를 사용하면 서로 다른 원소들이 같은 집합에 속해 있는지 아닌지를 판별할 수 있다.
두 원소가 Disjoint Set에 속하는지 아닌지 판별하기 위해서 union, find 연산을 사용한다.

Union-Find

union(x, y) : x가 속한 집합과 y가 속한 집합을 합친다. (합집합 연산)
find(x): x가 속합 집합의 대표값(루트 노드 값)을 반환. x의 최상위 부모가 누군인지 찾는 연산

Prim

프림 가중치-무방향 그래프에서 최소 스패닝 트리를 찾는 그리디 알고리즘이다.
임의의 시작 노드를 포함하는 트리에서 갈 수 있는 노드 사이의 간선 중 가장 가중치가 작은 것을 선택하고 그 노드를 트리에 포함시키면서 트리를 확장해 나가는 알고리즘이다.

코드(Kruskal)

import heapq

# x노드의 부모를 찾는 함수
# x의 노드의 최상위 부모는 자기 자신을 부모 노드로 가지고 있을 것
# 그런 노드를 찾을 때 재귀 호출을 종료함.
def find(parent, x):
    if x != parent[x]:
        parent[x] = find(parent, parent[x])
    return parent[x]

# 두 노드(n1, n2)가 같은 집합에 포함시키는 함수
def union(parent, n1, n2): 
    n1 = find(parent, n1) #n1: n1의 부모 노드
    n2 = find(parent, n2) #n2: n2의 부모 노드
    
    # 번호가 작은 노드(a)가 큰 번호(b)의 부모가 되도록
    # 한 노드가 다른 노드의 부모가 되는 식으로 만들어줘야 하는데
    # 번호가 작은 노드가 큰 노드의 부모가 되도록 규칙을 만듦
    if n1 < n2: 
        parent[n2] = n1 
    else:
        parent[n1] = n2

def solution(n, costs):
    parent = [i for i in range(n+1)] # --- 1️⃣ i번째 노드의 부모 노드를 남는 배열 
    								# 자기 자신을 부모 노드로 갖도록 초기화함.
    
    heap = []
    for n1, n2, c in costs:
        heapq.heappush(heap, [c, n1, n2]) # --- 2️⃣ 가중치 기준으로 minHeap을 생성
        
    answer = 0
    connected_edges = 0
    
    while heap:
        if connected_edges == n-1: # --- 3️⃣ ST: 간선의 개수 == 노드의 개수(N) - 1
            break
        c, n1, n2 = heapq.heappop(heap)
        if find(parent, n1) != find(parent, n2): # --- 4️⃣ 두 노드의 부모가 같지 않다면 == 사이클을 만들지 않음.
        										# 두 노드 모두 방문한 이력이 없는 경우거나, 
                                                # 한 노드(n1)만 방문한 이력이 있을 때, n2를 방문해도 전체 그래프에 사이클을 만들어지지 않는 경우 		
        										
            union(parent, n1, n2) # --- 5️⃣ n1, n2노드가 같은 집합에 포함됨을 표시
            answer += c
            connected_edges += 1
    return answer

코드(Prim)

import heapq 

def solution(n, costs):
    visited = [0] * (n+1)
    
    graph = [[] for _ in range(n+1)]
    
    for n1, n2, c in costs:
        graph[n1].append([c, n2])
        graph[n2].append([c, n1])
    
    start = costs[0][0] # 임의의 시작 노드
    heap = [[0, start]] # --- 1️⃣ 0: 시작노드에서 시작노드로 가는 비용은 0이므로, start: 시작 노드  
    					# heap에는 이미 방문한 노드에서 갈 수 있는 노드와 그 때의 비용이 저장되어 있다.
                        # heap은 간선의 가중치에 대한 minheap(최소힙)이다.
    
    answer = 0
    connected_node = 0
    
    while heap:
        if connected_node == n: # --- 2️⃣ 모든 노드를 방문한 경우
            break
        curCost, curNode = heapq.heappop(heap) 
        
        if not visited[curNode]: # --- 3️⃣ 아직 방문한 적 없는 노드에 대해
            connected_node += 1
            visited[curNode] = 1
            answer += curCost
            
            for elem in graph[curNode]: # 새롭게 방문한 노드로 갈 수 있는 노드와 그 노드로 갈 때 드는 비용을 heap에 추가한다. 
                heapq.heappush(heap, elem)
    return answer