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

문제

백준 - 1197번: 최소 스패닝 트리

분석

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

최소 스패닝 트리를 만드는 데 드는 가중치(비용)를 구하는 문제이다.

크루스칼 알고리즘을 이용하면 쉽게 구할 수 있다.

• 방법:

1. 간선의 가중치가 적은 순서대로 정렬한다.
2. 작은 간선 부터 MST에 추가할 수 있는지 확인한다. (간선 정보에 있는 노드 두 개의 대표 노드(부모)가 다른 지 확인한다.)
3. 추가 가능하면 간선 정보에 있는 노드 두 개를 union하고(MST에 추가), 총 가중치에 해당 간선의 가중치를 더한다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

v, e = map(int, input().split())
edges = []
for _ in range(e):
    a, b, c = map(int, input().split())
    edges.append((a, b, c))
edges.sort(key=lambda x:x[2])

def find(x):
    if x == uf[x]:
        return x
    uf[x] = find(uf[x])
    return uf[x]

def union(a, b):
    x = find(a)
    y = find(b)
    uf[x] = y

uf = [i for i in range(v+1)]
weight = 0
for a, b, c in edges:
    if find(a) != find(b):
        union(a, b)
        weight += c
print(weight)

끝으로..

크루스칼 알고리즘의 기초를 복습할 수 있는 문제였다.