[알고리즘][Python] 백준 1197 최소 스패닝 트리 문제 풀이

문제 출처 : www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

---

문제 해석 : 최소 신장 트리를 구하고 그 비용의 최솟값을 출력하는 문제이다.

 

문제 풀이 : 크루스컬 알고리즘을 이용하여 풀이할 수 있다.

---

풀이 코드

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


def make_union(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())
graph_all = []

parent = [0] * (V + 1)
for i in range(V + 1):
    parent[i] = i

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


graph_all.sort()
count = 0
answer = 0

while graph_all:
    if count == (V-1):
        break

    C,A,B = graph_all.pop(0)

    if find_parent(parent, A) == find_parent(parent, B):
        continue
    else:
        make_union(parent, A, B)
        count += 1
        answer += C
print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.