[Python] 프로그래머스 - 섬 연결하기

https://programmers.co.kr/learn/courses/30/lessons/42861

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

# 문제를 보자마자 최소 스패닝 트리(Minimum Spanning Tree)가 떠올랐다.

# 크루스칼 알고리즘으로 MST를 짰다.

 

def solution(n, costs):
    answer = 0
    # Union-Find함수
    def find(c):
        if par[c] == c:
            return c
        else:
            par[c] = find(par[c])
        return par[c]

    def union(a, b):
	    a, b = find(a), find(b)
	    par[max(a, b)] = min(a, b)
    # a와 b의 부모가 같은지 판단하는 함수
    def check(a, b):
        return find(a) == find(b)
    
    par = [i for i in range(n+1)]
    graph = [[] for _ in range(n)]
    # costs를 비용순으로 오름차순 정렬한다.
    costs.sort(key = lambda x: x[2])
    for i in costs:
        # 두 섬의 부모가 같지 않으면 연결되지 않은 것이므로, union을 통해 연결해주고
        # answer에 연결비용(i[2])를 더해준다.
        if not check(i[0], i[1]):
            union(i[0], i[1])
            answer += i[2]
            
    return answer

(프로그래머스 level: 3)