[BOJ/백준] 1197번 최소 스패닝 트리 - Python/파이썬 [해설/풀이]

📌 문제

---

📝 입력

---

💻 출력

---

📖 예제 입출력

---

📌 풀이

---

📖 해설

---

최소 스패닝 트리 = 최소 신장 트리
가장 적은 비용으로, 사이클 없이, 모든 정점을 연결하는 알고리즘

간선이 많으면 프림 알고리즘(Prim Algorithm) 사용
간선이 적으면 크루스칼 알고리즘(Kruskal Algorithm) 사용

본 문제에서는 크루스칼 알고리즘(Kruskal Algorithm)을 사용
크루스칼 알고리즘(Kruskal Algorithm)의 핵심은 Union-Find 알고리즘

쉽게 설명하면, 자기자신을 root 노드로 초기화하고
가중치가 작은 노드부터 각각 차례대로, 하나의 집합에 추가하며
집합에 추가된 노드는 집합 내 root 노드를 부모노드로 갱신한다.

즉, 아직 집합에 추가되지 않은 노드의 부모노드가,
이미 집합의 root 노드와 동일하다면, 사이클이 존재한다고 판단

💻 전체코드

---

V, E = map(int, input().split())

def find(n):
    if parent[n] != n:                  # 노드 n의 부모노드가 자기자신이 아니면
        parent[n] = find(parent[n])     # 노드 n의 부모노드 = 최상위 부모노드 탐색 재귀함수
    return parent[n]                    # 현재노드 n의 최상위 부모노드 return

def union(a, b):
    a = find(a)         	# 노드 a의 최상위 노드 탐색
    b = find(b)         	# 노드 b의 최상위 노드 탐색
    if a < b:           	# a < b 이면, 작은 값 a
        parent[b] = a   	# 노드 b의 부모노드 a로 갱신
    else:               	# a > b 이면, 작은 값 b
        parent[a] = b   	# 노드 a의 부모노드 b로 갱신


edges = []
parent = list(range(V + 1))
for _ in range(E):
    a, b, w = map(int, input().split())
    edges.append((a, b, w))
edges.sort(key=lambda x: x[2])  # 가중치 오름차순(낮은 순) 정렬

answer = 0
for a, b, w in edges:
    if find(a) != find(b):      # 노드 a의 최상위 노드 != 노드 b의 최상위 노드 -> 사이클이 아니면
        union(a, b)             # 최상위 노드 갱신
        answer += w             # 가중치 합산
print(answer)