n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.
def solution(n, costs):
costs.sort(key=lambda x: x[2])
union_list = [i for i in range(n)] # Union-Find 알고리즘을 위한 list 생성
answer = 0
for f, s, cost in costs:
if union_list[f] != union_list[s]: # 하나씩 꺼낸 cost 에서 첫번째 섬과 두번째 섬이 같은 union이 아니면
par = union_list[f]
child = union_list[s]
for i in range(n): # 자식 노드와 같은 값을 가지는 모든 노드의 값을 부모 노드의 값으로 변경
if union_list[i] == child:
union_list[i] = par
answer += cost
return answer