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

문제

• n개의 섬 사이에 다리를 건설하는 비용이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들자. 
  • 다리를 여러 번 건너더라도 도달만 할 수 있으면 통행 가능하다고 본다.
  • 1 <= 섬 개수 n <= 100
  • 다리 건설 비용의 개수 <= ((n-1) * n) / 2

 

풀이

• 최소 스패닝 트리 만들기
• edge 개수가 ((n-1) * n) / 2 이하이므로 크루스칼 알고리즘이 효율적임을 알 수 있다.

 

# 부모 찾기
def find(parent, x):
    if parent[x] != 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):    
    parent = [ i for i in range(n) ]    # 부모 테이블 자기 자신으로 초기화
    costs.sort(key=lambda x: x[2])      # cost 기준 정렬
    
    answer = 0	# 전체 비용
    for edge in costs:
        a, b, cost = edge
        if find(parent, a) != find(parent, b) :
            union(parent, a, b)
            answer += cost
    
    return answer

 

References

• 프로그래머스 고득점Kit 그리디