📚1. 문제 설명

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의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

입출력 예 설명

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

✏️2. 문제 풀이

섬 연결하기 문제를 풀이하기 위해서는 유니온-파인드와 크루스칼에 대해 알아야 한다.

Union Find

먼저 유니온 파인드(Union Find) 알고리즘은 유니온이라는 함수와 파인드라는 두 함수가 연결되어 있는 것과 같다.

• 파인드(Find) : 재귀적으로 부모를 계속 찾는다. 최종적으로 가장 상위의 루트(Root) 노드가 무엇인지 찾게 된다.
• 유니온(Union) : 두개의 서로 다른 노드의 부모가 같다면 두 노드를 합쳐준다. 노드간의 관계는 사라지지만 연결 정보는 확실하게 알 수 있게 된다.

어디와 어디가 연결되어 있는지 알고 싶을 때 사용하는 것이 유니온 파인드 알고리즘 이다.

Kruskal

크루스칼(Kruskal) 알고리즘은 그래프의 최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 알고리즘 중 하나이다. 최소 신장 트리란 그래프의 모든 노드를 연결하는 에지들의 가중치 합이 최소가 되는 트리를 말한다. 크루스칼 알고리즘은 탐욕적인 방법(greedy method)을 사용하여 문제를 해결한다.

크루스칼 알고리즘은 다음과 같은 단계로 수행된다.

1. 모든 에지를 가중치에 따라 오름차순으로 정렬한다.
2. 빈 결과 트리를 생성한다.
3. 정렬된 에지 목록을 순회하면서, 각 에지를 고려한다. 에지를 추가했을 때 사이클이 생성되지 않으면, 결과 트리에 해당 에지를 추가합니다. 그렇지 않으면 해당 에지를 무시한다.
4. 결과 트리에 포함된 에지의 개수가 노드의 개수에서 1을 뺀 값이 될 때까지 단계 3을 반복한다.

이제 두 알고리즘을 사용하여 문제를 풀어보자.

처음엔 아무것도 연결되어 있지 않은 상태이므로 각 노드가 모두 대표 노드이다. 따라서 자신의 인덱스값으로 초기화 해준다.

parent = [0] * n
    for i in range(n):
        parent[i] = i

이 부분은 union으로 각 노드가 속한 집합을 1개로 합치는 코드이다.

def setUnion(parent, a, b):
    fa = findParent(parent, a)
    fb = findParent(parent, b)

    if fa == fb:
        return
    else:
        parent[fb] = fa

1. a와 b의 find 함수를 통해 부모 노드를 찾고 비교한다.
2. 만약 서로의 부모가 같다면 return하여 함수를 종료한다.
3. 서로의 부모가 같지 않다면 b의 부모 노드를 a의 부모 노드로 변경한다.

이 부분은 find로 특정 노드 x에 관해 x가 속한 집합의 부모 노드를 반환하는 코드이다.

def findParent(parent, x):
    if parent[x] == x:
        return x
    else:
        return findParent(parent, parent[x])

1. 특정 노드 x와 그 노드를 index로 하여 리스트에 넣었을 때 나온 값이 동일한지 확인한다.
2. 만약 두 값이 같다면 특정 노드 x를 return 시킨다.
3. 다르다면 특정 노드 x를 index로 리스트에 넣었을 때 나온 값으로 find 함수를 다시 실행하여 같을 때까지 반복한다.
4. 부모 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드 값을 부모 노드 값으로 변경한다.

이 부분이 크루스칼을 이용해서 최소 비용을 구하는 코드이다.

costs.sort(key=lambda x: x[2])
    for a, b, cost in costs:
        if findParent(parent, a) != findParent(parent, b):
            setUnion(parent, a, b)
            answer += cost
    return answer

1. 먼저 costs 리스트를 비용을 기준으로 오름차순 정렬을 한다.
2. a와 b가 find 함수를 통해 각각 부모 노드를 확인한다.
3. 만약 각각 찾은 서로의 부모 노드가 같지 않다면 union 함수를 실행시키고 해당 비용을 answer에 더한다.

✅최종 코드

def findParent(parent, x):
    if parent[x] == x:
        return x
    else:
        return findParent(parent, parent[x])


def setUnion(parent, a, b):
    fa = findParent(parent, a)
    fb = findParent(parent, b)

    if fa == fb:
        return
    else:
        parent[fb] = fa


def solution(n, costs):
    answer = 0
    parent = [0] * n
    for i in range(n):
        parent[i] = i
    costs.sort(key=lambda x: x[2])
    for a, b, cost in costs:
        if findParent(parent, a) != findParent(parent, b):
            setUnion(parent, a, b)
            answer += cost
    return answer

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