[백준(BOJ)] #1197- 최소 스패닝 트리 (파이썬, Python3)

문제

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

1197번: 최소 스패닝 트리

 

 

---

문제 풀이

이 문제는 최소 신장 트리의 가중치를 구하는 문제로 크루스칼 알고리즘을 적용하여 풀었습니다.

 

2022.07.29 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 크루스칼(Kruskal) 알고리즘

[파이썬으로 배우는 알고리즘] 크루스칼(Kruskal) 알고리즘

 

입력으로 두 노드의 번호와 가중치가 들어오기 때문에 이 간선 정보를 사용하여 바로 크루스칼 알고리즘에 적용하였습니다.

 

문제 풀이에 대해 더 깊게 알고싶으신 분들은 위의 글에서 세세하게 설명하니 참고하시면 될 것 같네요!

 

---

구현

코드

import sys
input = sys.stdin.readline

def find(v):
    if v != root[v]:
        root[v] = find(root[v])
    return root[v]

def union(v1, v2):
    v1 = find(v1)
    v2 = find(v2)
    
    if v1 < v2:
        root[v2] = v1
    else:
        root[v1] = v2
        
def is_connected(v1, v2):
    v1 = find(v1)
    v2 = find(v2)
    
    if v1 == v2:
        return True
    else:
        return False

def kruskal():
    sum_w = 0
    edge_info.sort(key = lambda x: x[2])
    for v1, v2, weight in edge_info:
        if not is_connected(v1, v2):
            sum_w += weight
            union(v1, v2)
    return sum_w

if __name__ == "__main__":
    v, e = map(int, input().split())
    edge_info = list()
    root = list(range(v+1))
    for _ in range(e):
        edge_info.append(list(map(int, input().split())))
    print(kruskal())

결과