99클럽 코테 스터디 7일차 TIL 프로그래머스 섬 연결하기

프로그래머스 섬 연결하기

이 문제 카테고리가 그리디로 되어있지만, MST(Minnimum spanning Tree)를 알면, 쉽게 풀 수 있다.

MST를 구할때 두가지 방법이 있는데, heap 자료구조를 이용한 프림 알고리즘, 정렬을 활용한 크루스칼 알고리즘이 있다.

각 알고리즘을 간략하게 설명하자면 다음과 같다.

프림 알고리즘은 정점을 하나 잡고, 그 정점에서 연결할 수 있는 최소 비용의 간선을 연결시마다 갱신하며, 합쳐가는 알고리즘이다.

크루스칼 알고리즘은 모든 간선을 비용순으로 놓고, 비용이 작은 간선부터 연결하며, 사이클이 발생하지 않도록 (두 정점간에 하나의 경로만 있도록), 체크하며 정점들을 연결하는 알고리즘이다.

이 두 개 알고리즘을 모두 사용할 수 있지만,  일반적으로는 정점이 많이 주어지면 프림 알고리즘, 간선을 많이 사용한다면, 크루스칼 알고리즘으로 푸는게 좋다고 한다.

나의 코드

 

def solution(n, costs):
    # 간선 위주 => 크루스칼 알고리즘
    # 최소 비용의 간선순으로 사이클이 발생 하지 않도록 연결
    # 사이클 발생여부는 유니온 파인드로 확인.
    
    # 유니온 파인드 정의 구간
    group=[i for i in range(n)]
    def find(x):
        if group[x]!=x:
            group[x]=find(group[x])
        return group[x]
    
    def union(a,b):
        a,b=find(a),find(b)
        if a!=b:
            group[min(a,b)]=max(a,b)
            return True
        return False
    
    #deque 불러오기싫어서 역순으로 정렬
    answer = 0
    costs.sort(key=lambda x: -x[2])
    while costs:
        start,end,value=costs.pop()
        # 사이클이 발생하지 않는 연결이면
        if union(start,end):
            answer+=value
    return answer