[Python] 백준 1197번 : 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

---

💡 문제 풀이

최소 신장 트리 문제이다. 크루스칼로 해결했다.

 

가장 기본적인 문제로 알고리즘의 개념만 잘 숙지하고 있다면 해결할 수 있다.

✔️ 느낀 점

다음에는 크루스칼 외에 프림 알고리즘으로도 풀어봐야겠다.

💻 코드

import sys
input = sys.stdin.readline

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

parent = list(range(V+1))

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

def union(x,y):
    x = find(x)
    y = find(y)
    
    parent[y] = x

cnt, ans = 0, 0
while True:
    if cnt == V-1: break
    edge = edges.pop(0) # start, end, cost
    if find(edge[0]) != find(edge[1]):
        union(edge[0], edge[1])
        ans += edge[2]
        cnt += 1
    
print(ans)