알고리즘 스터디 - 백준 1197번 : 최소 스패닝 트리

문제 해석

그래프의 최소 스패닝 트리를 구하라

• 최소 스패닝 트리 : 모든 정점들을 연결하는 부분 그래프 중에서 가중치의 합이 최소인 트리

입력

1. V, E : 정점의 개수, 간선의 개수
2. A, B, C : A와 B 정점이 가중치 C로 연결되어 있음(C는 음수일 수 있다.)

어떤 알고리즘을 써야할까?

최소 비용 신장 트리에는 여러 가지 종류의 알고리즘이 존재하지만 중요한 것은 간선이 음수인 경우이다.

이 경우에는 "사이클"을 형성하지 않으면서 간선이 음수인 것도 알아야 하므로 크루스칼 알고리즘을 바로 적용하면 된다.

"크루스칼 알고리즘" 의 핵심 개념은 간선을 거리가 짧은 순서대로 그래프에 포함시키는 것이다. 즉, 모든 노드들을 최대한 적은 비용으로 '연결'만 시키면 되므로 모든 간선 정보를 오름차순으로 정렬한 뒤에 비용이 작은 간선부터 그래프에 포함시킨다.

알고리즘 코드

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

parent = {i : i for i in range(1, V+1)}
rank = {i : 0 for i in range(1, V+1)}
graph_edges = []

for _ in range(E):
    A, B, C = map(int, input().split())
    graph_edges.append([C, A, B])

# 해당 vertice의 최상위 정점을 찾기
def find(vertices):
    if parent[vertices] != vertices:
        parent[vertices] = find(parent[vertices])
    return parent[vertices]

def union(vertice1, vertice2):
    root1 = find(vertice1)
    root2 = find(vertice2)
    if root1 != root2:
        if rank[root1] > rank[root2]:
            parent[root2] = root1
        else:
            parent[root1] = root2
            if rank[root1] == rank[root2]:
                rank[root2] += 1

def kruskal(edges):
    mst = []
    edges.sort()

    for edge in edges:
        w, v1, v2 = edge
        if find(v1) != find(v2):
            union(v1, v2)
            mst.append(w)

    return sum(mst)

print(kruskal(graph_edges))