1197_최소스패닝트리

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

1197번: 최소 스패닝 트리

 

최소 스패닝 트리는 간선의 합이 가장 적은 트리이다.

 

이를 위해서는 아래와 같이 해결하면 된다.

 

먼저 가중치를 기준으로 해서 간선의 정보를 정렬한다.

 

만약 

 

1 2 3

2 3 2

1 3 1

 

와같이 입력이 들어온다면

 

1 3 1

2 3 2

1 2 3

 

과 같이 가중치가 작은 순으로 정렬을 해준다.

 

그 이후, 간선들과 연결된 노드들이 같은 트리에 있는지 확인한 후, 없다면 합쳐주면 된다.

 

이 과정에 이전에 배운 Union, find 을 사용하면 쉽게할 수 있다.

 

import sys
input = sys.stdin.readline

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

def union(a,b):
    a,b = find(a),find(b)
    if a> b:
        parents[a] = b
    else:
        parents[b] = a

v,e = map(int,input().split())
parents = [ i for i in range(v+1)]
way = []
for i in range(e):
    a,b,c = map(int,input().split())
    way.append((a,b,c))

way.sort(key=lambda x : x[2])
result = 0
for a,b,c in way:
    if find(a) != find(b):
        union(a,b)
        result += c
print(result)