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

문제

섬연결하기

섬을 연결하는데 cost가 있고, 최소비용을 구해야한다 -> 전형적인 크루스칼 문제이다

 

풀이

1. 먼저 " n개의 섬을 최소의 비용으로 서로 통행할 수 있게 만든다 " 에서 크루스칼 문제임을 알 수 있었다

2. costs 에 주어지는 값들은 [[x1,y1,cost], [x2,y2,cost] , ... , [xn,yn,cost]] 이렇게 생각하면 쉽다.

3. cost 기준으로 edges를 정렬한후 같은 집합에 속하지 않는 값들의 합을 구해서 반환하면 된다.

 

 

코드

# 크루스칼
def solution(n, costs):
    
    parent = [i for i in range(n+1)]
    
    def find(x):
        if x != parent[x]:
            parent[x] = find(parent[x])
        return parent[x]

    def union(a,b):
        a = find(a)
        b = find(b)
        if a<b:
            parent[b] = a
        else:
            parent[a] = b
    
    edges = []
    
    for i in costs:
        a,b,cost = i
        edges.append((cost,a,b))
    
    edges.sort()
    
    res = 0
    for i in edges:
        cost, a,b = i
        if find(a) != find(b):
            union(a,b)
            res += cost
        
    
    return res