[BOJ/Python] 1197. 최소 스패닝 트리

📌 문제

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

📌 문제 접근 방법

1. 크루스칼 알고리즘을 사용해서 구현하였다.
2. 가중치를 기준으로 오름차순 정렬한 후,
   정렬된 순서대로 간선을 선택하여 사이클이 만들어지지 않는다면 (간선에 연결된 노드 2개가 같은 집합이 아니라면) 노드를 연결하고 가중치를 total에 더해준다.

 

📌 코드

# 백준 1197 최소 스패닝 트리

def find_set(x):
    if x != parents[x]:
        parents[x] = find_set(parents[x])
    
    return parents[x]


def union(x, y):
    root_x = find_set(x)
    root_y = find_set(y)

    if rank[root_x] >= rank[root_y]:
        parents[root_y] = root_x
        if rank[root_x] == rank[root_y]:
            rank[root_x] += 1
    else:
        parents[root_x] = root_y


def kruskal():
    total = 0

    for a, b, w in edges:
        if find_set(a) != find_set(b):
            total += w
            union(a, b)

    return total


V, E = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(E)]
edges.sort(key=lambda x: x[2])

parents = [x for x in range(V+1)]
rank = [0 for _ in range(V+1)]

print(kruskal())