백준 1197번 <최소 스패닝 트리>

백준 알고리즘 1197번

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

1197번: 최소 스패닝 트리

---

1197번

입력으로 첫 줄에 정점의 수 V와 간선의 수 E가 주어진다. 그리고 E줄에 걸쳐 간선의 정보가 주어진다.

이때 세 정수 A, B, C가 들어온다. 이는 A번 정점과 B번 정점이 연결된 간선의 weight가 C라는 의미이다.

 

출력으로는 최소 스패닝 트리의 weight를 출력하면 된다.

---

문제 해결

최소 스패닝 트리 알고리즘의 대표적인 예인 크루스칼 알고리즘을 활용하였다.

 

크루스칼 알고리즘은 edge를 weight가 작은 순으로 정렬하여 작은 것부터 Cycle이 생기지 않으면 선택하는 알고리즘이다. (탐욕 알고리즘을 기초로 하고 있다.)

 

크루스칼 알고리즘을 효율적으로 구현하기 위해서는 다른 알고리즘이 필요하다.

Union-Find 알고리즘을 사용하여 Disjoint Set을 표현하여야 한다.

 

edge를 정렬하기 위해 우선순위 큐를 사용하였다. edge를 모두 우선순위 큐에 넣고 하나씩 빼서 사용하였다. 

---

코드

import heapq

def find(node):
    if parent[node] == node:
        return node
    return find(parent[node])

def union(a, b):
    find_a = find(a)
    find_b = find(b)
    if rank[find_a] > rank[find_b]:
        parent[find_b] = find_a
    elif rank[find_b] > rank[find_a]:
        parent[find_a] = find_b
    else:
        if find_a > find_b:
            parent[find_a] = find_b
            rank[find_b] += 1
        else:
            parent[find_b] = find_a
            rank[find_b] += 1

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

graph = []

parent = [i for i in range(v+1)]
rank = [0 for _ in range(v+1)]
for _ in range(e):
    a, b, weight = map(int, input().split())
    heapq.heappush(graph, [weight, a, b])

result = 0

while graph:
    weight, a, b = heapq.heappop(graph)
    if find(a) != find(b):
        union(a, b)
        result += weight


print(result)

---

결과

---