최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용 구하기.
n | costs | return |
---|---|---|
4 | [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] | 4 |
: 최소비용. 모두연결 ➡ 크루스칼
유니온 파인드 이용하여 구현.
def solution(n, costs):
def find(v):
if v == root[v]:
return v
else:
y = find(root[v])
root[v] = y
return root[v]
def union(a, b):
a = find(a)
b = find(b)
if a<b:
root[b] = a
else:
root[a] = b
root = [i for i in range(n)]
graph = []
for s, e, w in costs:
graph.append((w, s, e))
graph.sort(key=lambda x : x[0])
sumi = 0
for w, s, e in graph:
if find(s) != find(e):
union(s, e)
sumi += w
return sumi