[Greedy, MST] 섬 연결하기 - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/42861?language=python3 

코딩테스트 연습 - 섬 연결하기

 

본 문제는 MST(Minimum Spanning Tree) 문제로,

MST를 푸는 대표적인 방법인 Kruskal과 Prim 알고리즘으로 풀 수 있습니다.

 

MST에 대해서는 추후에 자세하게 다루도록 하겠습니다. 

 

저는 본 문제를 크루스컬 알고리즘을 활용하여 풀었습니다. 크루스컬은 Union Find 알고리즘을 통해 Cycle을 체크하였고 기존 path를 정렬하여 가장 path가 적은것부터 탐욕적으로 선택하는 방법으로 문제를 풀었습니다.

 

최종 코드는 다음과 같습니다.

 

Kruskal 알고리즘을 사용한 구현 코드

class DisjointSet :
    def __init__(self, n) :
        self.parent = {}
        self.rank = {}
        for i in range(n) :
            self.parent[i] = i
            self.rank[i] = 0

    def Find(self, v) :
        if self.parent[v] != v :
            self.parent[v] = self.Find(self.parent[v])
        return self.parent[v]

    def Union(self, root1, root2) :
        if self.rank[root1] > self.rank[root2] :
            self.parent[root2] = root1
        else :
            self.parent[root1] = root2
            if self.rank[root1] == self.rank[root2] :
                self.rank[root2] += 1

def kruskal(n, info) :
    minimum_weight = 0
    disjointset = DisjointSet(n)
    result = []
    for data in sorted(info, key = lambda cost: cost[2]) :
        v, u, weight = data
        root1 = disjointset.Find(v)
        root2 = disjointset.Find(u)
        if root1 != root2 :
            disjointset.Union(root1, root2)
            result.append(data)
            minimum_weight += data[2]
    return result, minimum_weight

def solution(n, costs):
    answer, minimum_weight = kruskal(n, costs)
    return minimum_weight