프로그래머스 - 섬 연결하기 (Greedy) / Level 3

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

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

 

문제 설명

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

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

 

 

제한 사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2 이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

 

입출력 예시

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

 

입출력 예 설명

 

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

 

풀이

def solution(n, costs):  # kruskal 알고리즘

    islands = [i for i in range(n)]
    edges = 0
    min_cost = 0
    
    costs.sort(key = lambda x : x[2])  # edge의 weight 기준으로 오름차순 정렬.
    
    while edges != n-1:
        cost = costs.pop(0)
        if find_root(islands, cost[0]) != find_root(islands, cost[1]):  # cycle 이루는지 체크.
            union_node(islands, cost[0], cost[1])
            edges += 1
            min_cost += cost[2]
        
    return min_cost

def find_root(root_nodes, node):  # 경로 압축
    if root_nodes[node] != node:
        root_nodes[node] = find_root(root_nodes, root_nodes[node])
    return root_nodes[node]

def union_node(root_nodes, a, b):  # 두 vertex 이어주기.
    a = find_root(root_nodes, a)
    b = find_root(root_nodes, b)
    
    root_nodes[b] = a

이 문제는 그 유명한 MST(Minimum Spanning Tree) 문제이다. 우리말로 최소 신장 트리 문제이다.

해당 문제의 전형적인 알고리즘으로는 "Prim" 알고리즘과 "Kruskal" 알고리즘이 있다.

 

그중 Kruskal 알고리즘으로 풀기 위해서 cost에 따라서 오름차순으로 정렬하여

가장 낮은 cost의 edge를 선택하기로 하였다.

선택할 때 cycle을 이루지 않게 하는 것이 kruskal 알고리즘의 핵심인데

그것을 판단하기 위해서  union-find 알고리즘을 사용했다.

find는 어느 한 노드에 대하여 그 노드의 root 노드를 찾아주는 함수를 말하고

union은 두 노드에 대하여 각자의 root노드를 구하고

특정한 우선순위에 따라 하나를 다른 하나의 자식 노드로 편입시킨다.

즉, 두 개의 트리를 하나의 트리로 합병시키는 것이다.

 

여기서 핵심은 Cycle을 만들지 않기 위해서 root노드가 서로 다를 때만 union 시켜준다는 것이다.

두 노드의 root 노드가 같은데 연결시켜버린다면 필연적으로 cycle을 이룰 수밖에 없다.