[Baekjoon] 1197번 : 최소 스패닝 트리 (Python, 최소 신장 트리)

[Baekjoon] 1197번 : 최소 스패닝 트리 (Python, 최소 신장 트리)

 

목차

 

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

1197번: 최소 스패닝 트리

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

Python

 

방법 1 - 메모리 46980KB / 시간 344ms / 코드 길이 528B

 

본 문제는 대놓고 최소 신장 트리를 구하도록 유도한 문제이다.

이에 따라 본 문제를 크루스칼 알고리즘에 의거한 문제를 풀어내면 된다.

각 노드마다의 parent root를 저장하는 p list

가중치가 최소가 되는 MST를 위해 cost 비용을 정렬하여 기입하는 edges list

 

정렬된 edges를 기반으로 cycle이 없는지 확인하고 만약 cycle이 아니라면 parent node를 작은 값에 맞추는 작업을 진행한다.

 

 

import sys
input = sys.stdin.readline

def f_p(p, x):
    if p[x] != x:
        p[x] = f_p(p, p[x])
    return p[x]

def union(p, a, b):
    a = f_p(p, a)
    b = f_p(p, b)
    if a < b:
        p[b] = a
    else:
        p[a] = b

v, e = map(int, input().split())
edges=[]
for i in range(e):
    a, b, c = map(int, input().split())
    edges.append((c,a,b))
edges.sort()

p = [i for i in range(v+1)]
res = 0
for edge in edges:
    c, a, b = edge
    if f_p(p, a) != f_p(p, b):
        union(p, a, b)
        res += c
print(res)