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

🗃️문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

🖥️코드

# 주어진 노드가 집합 안에 포함이 되는지를 확인
def find(parent, x):
    if parent[x] == x:
        return x
    parent[x] = find(parent, parent[x])
    return parent[x]

# 합집합 연산
def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    # 작은 쪽에 맞추기
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def solution(n, costs):
    answer = 0  # 비용
    parent = [i for i in range(n+1)]
    costs = sorted(costs, key=lambda x : x[2])  # 비용 순으로 정렬
    for cost in costs:
        # 부모가 일치하지 않으면 합집합 연산을 수행하도록
        if find(parent, cost[0]) != find(parent, cost[1]):
            union(parent, cost[0], cost[1])
            answer += cost[2]
    return answer

🔒문제 출처

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