프로그래머스 - 섬연결하기 (파이썬)

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

 

문제설명

n개의 섬 사이에 다리를 건설하는 비용이 주어지고,

모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 구한다.

그래프에서 최소비용으로 모든 노드를 연결할 수 있는 최소신장트리를 찾는 문제이다.

 

문제풀이

1. 크루스칼 알고리즘 사용

# 부모 노드를 찾기 위한 함수
def find(parent,x):
    if parent[x]==x:
        return x
    else:
        return find(parent,parent[x])

# 부모 노드가 다를 경우 두 노드가 속한 집합을 합침 (두 집합에 간선을 연결한다고 생각하기)
def union(parent,a,b):
    root_a=find(parent,a)
    root_b=find(parent,b)
    # 부모 노드는 무조건 작은 값을 기준으로 지정
    if root_a<root_b:
        parent[root_b]=root_a
    else:
        parent[root_a]=root_b
    
def solution(n, costs):
    answer=0
    
    # 부모노드를 자기 자신으로 초기화
    parent=[i for i in range(n)]
    
    # costs 배열에서 2번째 값을 기준으로 오름차순 정렬
    costs=sorted(costs,key=lambda x:x[2])
    
    for n1,n2,cost in costs:
        # 부모 노드가 같지 않을 경우(=사이클이 발생하지 않는 경우)에만 집합에 포함
        if find(parent,n1) != find(parent,n2):
            answer+=cost
            union(parent,n1,n2)
    return answer