[프로그래머스 | 파이썬 python] [크루스칼 알고리즘] 섬 연결하기

🌏 문제

프로그래머스

 

👽 풀이

크루스칼 알고리즘을 이용한 풀이

def find_parent(parent, a):
    if parent[a] != a:
        parent[a] = find_parent(parent, parent[a])
    return parent[a]

def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)

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

 

💫 크루스칼 알고리즘 (Kruskal Algorithm)

크루스칼 알고리즘은 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키는 알고리즘이다. 이때, 사이클을 발생시킬 수 있는 간선의 경우, 집합에 포함시키지 않는다.