[프로그래머스]level3-섬 연결하기-Python[파이썬]

문제링크

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

문제설명

알고리즘

크루스칼 알고리즘 사용하면 된다.

• 모든 노드들을 가장 적은 수의 간선과 비용으로 연결

코드

# 크루스칼 알고리즘
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    p_a = find_parent(parent, a)
    p_b = find_parent(parent, b)
    if p_a < p_b:
        parent[p_b] = p_a
    else:
        parent[p_a] = p_b
        
def solution(n, costs):
    parent = [i for i in range(n)]
    graph = []
    for a, b, cost in costs:
        graph.append((cost, a, b))
    graph.sort() # [[1, 0, 1], [1, 1, 3], [2, 0, 2], [5, 1, 2], [8, 2, 3]]
    total_sum = 0
    for cost, a, b in graph:
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
            total_sum += cost
    
    return total_sum