293. 최소 스패닝 트리
1) 어떤 전략(알고리즘)으로 해결?
MST (Kruskal)
2) 코딩 설명
- mst 크루스칼 방식은 최소 스패닝 트리를 구성하는 것입니다.
- 스패닝 트리란 모든 노드들이 이어져있게 하는 상태를 의미하는데, 이 노드들을 이을 때 가장 최소의 비용을 들여 모든 노드들을 이어주는 것을 최소 스패닝 트리를 구성하는 것이라고 합니다.
- 이를 구현하기 위해서는 노드 사이를 잇는 간선들에 대한 정보를 입력하고 저장해두는데, 비용이 적은 순으로 힙에 넣어둡니다.
- 그리고 이 힙에서 하나씩 pop을 진행해줍니다. 그렇게되면 가장 비용이 적은 간선부터 나오게 되겠죠?
- 이 비용이 적은 노드들 부터 이제 "이 두 노드를 이 간선으로 진짜 이어주겠다!" 라는 "등록"의 과정을 수행해줄 것입니다.
- 이때 "등록"을 수행할 때 주의해야할 점은, 노드를 간선으로 이으려고 할 때 이미 등록이 완료된 간선들과 "사이클"을 이루는 지 여부를 확인해야 합니다.
- "사이클"을 이루는 지 여부는
union-find방식을 통해서 판별하면 됩니다. union-find에서 find 함수를 통해 자신의 최종 조상과 상대 노드의 최종 조상을 비교했을 때 서로 다를 경우에만 간선을 이어주는 "등록"의 과정을 거쳐야 합니다. "등록"은 둘의 최종 조상을 union 해주면 됩니다.- 만약 조상이 같다면 사이클이 생기게 되므로 이 경우에는 건너뛰면 됩니다.
<내 풀이>
import heapq
import sys
v,e = map(int, sys.stdin.readline().rstrip().split())
edge = []
answer = []
for _ in range(e) :
a,b,c = map(int, sys.stdin.readline().rstrip().split())
heapq.heappush(edge, (c,a,b)) # 가장 낮은 가중치의 간선들
parent = [0 for _ in range(v+1)]
# parent = [i for i in range(V+1)]
for i in range(1,v+1) :
parent[i] = i
def find(x) :
if parent[x]!=x :
parent[x]=find(parent[x])
return parent[x]
def union(a,b) :
if a<b :
parent[find(b)] = find(a)
else :
parent[find(a)] = find(b)
while edge :
now_cost, now_a, now_b = heapq.heappop(edge)
# 가장 최소 비용의 간선 꺼내기 &
# 구성하는 두 노드가 싸이클을 이루지 않으면 얘네 둘을 이어주기
if find(now_a)!=find(now_b) :
# find 를 했을 때 다르면 사이클은 발생하지 않는다.
union(now_a,now_b)
answer.append(now_cost)
print(sum(answer))
<반성 점>
- union find 를 구현할 때 find 함수에서 자꾸 실수를 한다.
- 두 개를 비교할 때
a=find(a)&b=find(b)로 최종 조상 간 비교 - 최종 조상들 중 더 작은 쪽을 바꿀건데
parent(a) = b의 형태로 변경해주기 !! - 즉 최종 조상의 부모를 상대의 최종 조상으로 갱신시켜주면 된다.
