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

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

1197번: 최소 스패닝 트리

 

 

문제 해결 포인트

- 문제 이름에서 알 수 있듯 최소 스패닝 트리 알고리즘 문제입니다.

- parent : 서로소 집합 개념에서 각 정점이 어느 집합에 속해있는지 정보를 저장

- edges : 간선의 정보를 저장하는 공간. 가장 작은 비용이 발생하는 간선부터 연결해나간다

- find_parent : 해당하는 정점의 부모(집합)을 찾아주는 함수

- union_parent : 두 정점에 대해서 같은 부모(집합)에 속할 수 있도록 연산. 더 작은 값이 부모가 된다.

 

작성 코드

import sys
input = sys.stdin.readline
V, E = map(int, input().split())
edges = []  # 간선 정보를 담을 공간

for i in range(E):
    a, b, w = map(int, input().split())
    edges.append((w, a, b))  # '간선 비용' 기준으로 정렬을 위해 (비용, 정점, 정점) 형태로 저장

def find_parent(x):  # 서로소 집합 부모 확인
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]

def union_parent(a, b):  # 서로소 집합 그룹 연산
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

parent = [i for i in range(V+1)]  # 자기 자신을 부모로 갖는 서로소 집합
edges.sort()  # 간선 비용 기준 올림차순으로 정렬
result = 0

for w, a, b in edges: 
    if find_parent(a) != find_parent(b):  # 사이클이 생기지 않는다면
        union_parent(a, b)  # 간선 연결
        result += w  # 비용 계산

print(result)

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

 

---

REFERENCE

<이것이 취업을 위한 코딩테이스다 with Python>