문제 설명
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):
costs = sorted(costs, key=lambda x:x[2])
parents = [i for i in range(n)]
def find_parent(parents, x):
if parents[x] != x:
parents[x] = find_parent(parents, parents[x])
return parents[x]
def union_elems(parents, x, y):
x = find_parent(parents, x)
y = find_parent(parents, y)
if x < y:
parents[y] = x
else:
parents[x] = y
answer = 0
for a,b,cost in costs:
if find_parent(parents, a) != find_parent(parents, b):
answer += cost
union_elems(parents, a, b)
return answer