[프로그래머스] 섬 연결하기 (python,파이썬)

 

모든 섬을 통행 가능하도록 만들 때 최소 비용을 구하는 문제이다. 최소 신장 트리 (MST)를 활용하는 문제이다.

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

def union(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):
    parent=[0]*n
    for i in range(n):
        parent[i]=i
    costs.sort(key=lambda x : x[2])
    total_cost=0
    v=0
    for i in range(len(costs)):
        a,b,cost=costs[i]
        if find_parent(parent,a) != find_parent(parent,b):
            union(parent,a,b)
            total_cost+=cost
            v+=1
            if v == n-1:
                break
        
    return total_cost

내가 사용한 알고리즘은 크루스칼 알고리즘이다.

• 정점의 갯수만큼 부모 리스트를 생성한다. 모든 정점의 초기 부모는 자기 자신이다.
• 모든 간선을 비용을 기준으로 오름차순 정렬 한다. costs정렬
• costs를 순회하며 간선을 하나씩 확인한다.
• 정점a와 정점b의 부모가 다르면 union을 통하여 부모를 같게 한다.
  • 그 간선의 cost를 total_cost에 더한다.
  • 간선의 갯수 v를 1늘린다.
• 정점a와  정점b의 부모가 같으면 이미 연결된 것이다.
• 최소 신장 트리의 간선의 갯수는 (정점의 갯수 -1)이다. 간선의 갯수가 (정점의 갯수 -1)과 같으면 종료한다.