[프로그래머스 | Python] 섬 연결하기

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

'최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return' 하는 문제다
모든 섬+최소 비용 = 트루스칼 알고리즘 이므로 이코테를 공부하면서 익혀뒀던 방법을 사용했다

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 = [0]*n
    graph = []
    for i in range(n):
        parent[i] = i
    
    for a,b,cost in costs:
        graph.append((cost,a,b))
        
    graph.sort()
    for cost,a,b in graph:
        if find_parent(parent,a)!=find_parent(parent,b):
            answer += cost
            union_parent(parent,a,b)
            
    return answer