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

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

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

Spanning Tree(신장트리)문제입니다.

이러한 신장트리 문제에서는 Prim이나 Kruskal 알고리즘을 사용한다고 합니다. (하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분그래프)

문제부터 간단하게 요약하면, 

 

다음 그림과 같이 섬들을 연결하려 하는데, 모든 섬들을 연결하면서, 최소 비용으로 다리를 건설할 때 최소 비용을 return하는 문제입니다. 

위의 그림과 같은 상황에서는 초록색 선들을 연결해서 건설하는 것이 가장 효율적인 방법임을 알 수 있습니다. 

 

즉 solution(n, costs)에 

n : 섬의 개수

costs : 섬a, 섬b, 비용을 담는 array

가 input으로 들어갈 때 

 

모든 섬들을 연결하는 최소비용을 return하여야 합니다. 

 

<Solution>

이 문제의 아이디어는 Kruskal 알고리즘을 사용하는 것입니다. Kruskal 알고리즘을 설명할 때 흔히 드는 문제가 이 문제와 정확하게 일치하기에 구현 또한 같은 방식으로 진행하였습니다. 일종의 Greedy 알고리즘으로 실제 알고리즘의 작동방식은 아래와 같습니다.

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2. 간선을 하나씩 확인하며 현재의 간선이 cycle 을 발생시키는지 확인한다. 2-1. cycle이 발생한다면, 최소 신장 트리에 포함시키지 않는다. 2-2. cycle이 발생하지 않는다면, 최소 신장 트리에 포함시킨다. 3. 모든 간선에 대해 2의 과정을 반복한다.

 

실제 코드구현은 아래와 같습니다.

#Spanning Tree using Kruskal algorithm
def find_parent(parent ,x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a<b:
        parent[b] = a
    else:
        parent[a] = b

def Sort(sub_li): # sort by cost
    sub_li.sort(key = lambda x: x[2])

def solution(n, costs):
    parent = [0]*(n+1)
    answer = 0
    for i in range(1, n+1):
        parent[i] = i
    
    Sort(costs)

    for e in costs:
        a, b, cost = e
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b)
            answer += cost

    return answer