BOJ - 1922

백준 문제 링크
네트워크 연결

❓접근법

1. 크루스칼 알고리즘 문제.
   -> 최소 신장 트리를 만드는데 필요한 비용을 구할 때
2. find_parent, union_parent 함수를 만들어준다.
3. 루트 노드를 찾을 find_parent 함수와
   두 원소가 속한 집합을 합칠 union_parent 함수가 필요하다.
   간선 데이터를 넣을 리스트 egdes,
   최소 비용을 저장할 result 변수가 필요하다.
4. 간선 데이터를 비용에 따라 오름차순 정렬하고,
   하나씩 확인하며 정점 a와 b가 사이클을 발생시키지 않으면
   최소 신장트리에 포함시키고, result += cost
   마지막으로 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
        
n = int(input())
m = int(input())

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

edges = []
result = 0

for _ in range(m):
    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)