[프로그래머스 level3 섬 연결하기] 크루스칼 알고리즘 활용하기

해결해야하는 문제는 다음과 같았다.

https://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):
    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 = [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(parent,a,b)
            answer += c
    return answer