BOJ - 1197

백준 문제 링크
최소 스패닝 트리

❓접근법

1. 스패닝 트리 = 신장 트리
2. 문제에서 요구하는 것은 최소 스패닝 트리
   -> 크루스칼 알고리즘
   크루스칼 알고리즘의 과정은 다음과 같다.

• 간선 데이터를 비용에 따라 오름차순 정렬
• 간선을 하나씩 확인하여 현재의 간선이 사이클을 발생시키는지 확인
• 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
• 사이클이 발생하는 경우 최소 신장 트리에 포함 x
• 모든 간선에 대해 위 과정을 반복함

3. 루트 노드를 찾을 find_parent 함수와
   두 원소가 속한 집합을 합칠 union_parent 함수가 필요하다.
4. 간선 데이터를 넣을 리스트 egdes,
   최소 비용을 저장할 result 변수가 필요하다.
5. 간선 데이터를 비용에 따라 오름차순 정렬하고,
   하나씩 확인하며 정점 a와 b가 사이클을 발생시키지 않으면
   최소 신장트리에 포함시키고, result += cost.
6. 마지막으로 result를 출력하면 끝!

👌🏻코드

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        

v, e = map(int, input().split())

parent = [i for i in range(v + 1)]

edges = []
result = 0

for _ in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))
    
edges.sort()

for edge in edges:
    cost, a, b = edge
    
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost
        
print(result)