[프로그래머스] [그리디][최소신장트리][크루스칼 알고리즘] 섬 연결하기

섬 연결하기

프로그래머스

 

• 풀이
  • 처음에 heap과 bfs를 써서 풀었음
    • -> 이 문제는 목적지가 있는 것이 아니기 때문에 bfs가 될 수 없음
  • MST( Minimum Spanning Tree ) : 최소 신장 트리
    • 가장 낮은 가중치 값들로 간선이 이루어진 트리
    • 낮은 간선부터 연결하는데, 두 섬을 연결함으로 인해 사이클이 발생하는지 확인해야함
      • 사이클 확인 과정: union-find
      • union 하는데 이미 두 섬의 부모가 같으면 사이클 발생
    • 사이클이 발생하지 않는 선에서 낮은 가중치를 더해가면 최소신장트리가 구성됨

 

def solution(n, costs):
    
    def union(x,y):
        a=find(x)
        b=find(y)

        if a==b:
            return False #사이클 발생
        
        if a<b:
            root[b]=a
        else:
            root[a]=b
        return True

    def find(x):
        if root[x]!=x:
            root[x]=find(root[x])
        return root[x]
    
    
    root=[i for i in range(n)]
    costs.sort(key=lambda x:x[2])
    answer = 0
    
    for cost in costs:
        s,e,v=cost
        
        if union(s,e): #사이클 발생안하면
            answer+=v
    
    return answer