n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.
costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.
크루스칼 알고리즘
을 사용할 수 있겠습니다.Union-Find
알고리즘도 사용해야 합니다.key
파라미터에 원하는 기준원소를 넘겨서 가중치 기준으로 오름차순 정렬이 가능합니다.parent
배열을 초기화합니다.def solution(n, costs):
answer = 0
#비용을 기준으로 오름차순 정렬
costs.sort(key = lambda x: x[2])
#부모 리스트
parent = [i for i in range(n)]
#find함수
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
#union함수
def union(a, b):
a, b = find(a), find(b)
if a < b:
parent[b] = a
else:
parent[a] = b
for src, dest, cost in costs:
if find(src) != find(dest):
union(src, dest)
answer += cost
return answer