프로그래머스 섬연결하기(Lv3)

문제

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

풀이

def solution(n, costs):
    
    def find(f,x):
        if f[x] == x:
            return x
        
        f[x] = find(f,f[x])
        return f[x]
    
    def union(f,a,b):
        a = find(f,a)
        b = find(f,b)
        
        if a == b: return 0
        
        elif a<b:
            f[b] = a
        else:
            f[a] = b
    
    answer = 0
    costs.sort(key = lambda x:x[2])  #거리 기준 정렬
    
    f = [i for i in range(n+1)]
    count = 0
    
    for cost in costs:
        a,b,c = cost
        
        if union(f,a,b) == 0: #이미 탐색한 곳이면 패스
            continue
            
        else :
            answer += c
            count += 1
        
        if count == n-1:
            return answer
   
    return answer

공부한것

크루스칼 알고리즘
공부하면서 이런게 크루스칼이라는것을 알게되었다.
예전에 보고 이름만 기억하고 있던거였는데 최소 그래프 만들때 알아두면 좋을것같다

출처 : https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html