프로그래머스: 섬 연결하기

섬을 연결하는 최소 비용을 구하는 문제로, 최소 신장 트리 문제에 해당된다.

자연스럽게 크루스칼 알고리즘을 떠올릴 수 있다.

최소 신장 트리 혹은 크루스칼 알고리즘이 궁금하다면, 아래 링크로!

(간단히 말하자면, 크루스칼 알고리즘은 비용이 가장 적게 드는 edge부터 연결시켜가는 알고리즘이다)

https://focalpoint.tistory.com/15

신장 트리, 최소 신장 트리, Kruskal Algorithm

def solution(n, costs):
    def find_parent(parent, x):
        if parent[x] == x:
            return x
        parent[x] = find_parent(parent, parent[x])
        return parent[x]
    def union(parent, a, b):
        a = find_parent(parent, a)
        b = find_parent(parent, b)
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
    
    answer = 0
    
    parent = [i for i in range(n)]
    costs.sort(key=lambda x: x[2])
    for cost in costs:
        a, b, c = cost
        if find_parent(parent, a) != find_parent(parent, b):
            union(parent, a, b)
            answer += c
    
    return answer