[프로그래머스] 섬 연결하기 [탐욕법, Minimum Spanning Tree]

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

문제 해석

문제 설명을 읽어보면 의도를 알 수 있습니다. 문제에서 요구하는 바는 다리 건설에 드는 비용이 가장 작게 만들고, 사이클은 형성되지 않아도 됩니다. 자료구조, 알고리즘 때 익혔던 MST, Minimum Spanning Tree가 생각나는 문제입니다. 우리는 Edge의 형태가 필요한 게 아니고 Cost만 계산하면 되기 때문에 형태는 더욱 간단해집니다.

MST를 만드는 방법

1. Kruskal Algorithm

Kruskal Algorithm의 과정은 다음과 같습니다.

• 그래프의 Edge를 Cost(Weight)가 작은 순서대로 정렬합니다.
• 정렬된 Edge를 순회하며 해당 Edge를 MST에 포함했을 때 사이클을 형성하는지 체크합니다.
• 사이클을 형성하지 않는 Edge를 MST에 포함합니다.

정렬은 각 언어에서 기본으로 제공하며, Edge를 MST에 포함하는 방법도 간단합니다. 사이클을 형성하는지 체크하는 부분이 가장 중요하며, 이를 확인하기 위해 union-find 함수를 이용합니다.

def union(root1, root2):
    global disjunctionSet
    disjunctionSet[root2] = root1
    for i in range(len(disjunctionSet)):
        if disjunctionSet[i] == root2:
            disjunctionSet[i] = root1

def find(vertex):
    global disjunctionSet
    
    if disjunctionSet[vertex] == -1:
        return vertex
    
    return disjunctionSet[vertex]

union 함수는 두 트리를 하나로 합치는 역할을 합니다. root2가 root1에 종속되며, root2를 가리키던 모든 요소를 root1을 가리키도록 변경합니다. union 함수를 통해 집합에 포함될 때 트리의 depth를 늘리지 않고, 최상단 노드에 포함되도록 만들었습니다.

find 함수는 자신이 속한 트리의 최상단 노드 값을 반환합니다. union 함수의 형식 상 depth가 최대 2이기 때문에 O(1)로 바로 찾아낼 수 있습니다.

2. Prim Algorithm

Prim Algorithm은 시작점을 지정한 후 출발하여 트리를 단계적으로 확장하는 방법이며, 과정은 다음과 같습니다.

• 시작점을 지정하여 트리에 포함합니다.
• 인접점 중 트리에 포함되지 않았으며, 가장 Cost가 낮은 Edge로 이어진 점을 선택하여 트리에 포함합니다.
• 트리가 n-1 개의 Edge를 가질 때까지 반복합니다.
• 위 과정을 시작점을 변경해가며 모든 점에 대해 반복합니다.

참고사항

Kruskal Algorithm의 시간 복잡도는 Edge를 정렬하는 시간에 좌우되며, 가장 효율적인 경우 O(E log E)가 됩니다. (E = number of Edge) 반면 Prim Algorithm의 시간 복잡도는 O(n^2), n = number of vertex이며, 문제와 같이 그래프에 Edge의 수가 ((n-1) * n) / 2개 이하로 존재하는 경우에는 Kruskal Algorithm이 더욱 유리합니다.

풀이

def union(root1, root2):
    global disjunctionSet
    disjunctionSet[root2] = root1
    for i in range(len(disjunctionSet)):
        if disjunctionSet[i] == root2:
            disjunctionSet[i] = root1

def find(vertex):
    global disjunctionSet
    
    if disjunctionSet[vertex] == -1:
        return vertex
    
    return disjunctionSet[vertex]

def solution(n, costs):
    global disjunctionSet
    disjunctionSet = [-1 for _ in range(n)]
    
    answer = 0
    costs.sort(key=lambda x: x[-1])
    
    for v1, v2, cost in costs:
        root1 = find(v1)
        root2 = find(v2)
        
        if root1 == root2:
            continue

        union(root1, root2)
        answer += cost
        
    return answer

 

Kruskal Algorithm으로 구현한 풀이입니다. 최초 disjunctionSet은 모든 노드가 root인 경우로 생각하여 -1로 초기화합니다. costs를 비용을 기준으로 정렬한 뒤 루프를 수행합니다. root1과 root2가 동일한 경우에는 cycle이 형성되었다는 의미이므로 넘어갑니다. 그렇지 않은 경우에는 union을 수행하고, cost를 증가시켜 줍니다.