[baekjoon] 백준 1197번(파이썬): 최소 스패닝 트리

문제

1197번: 최소 스패닝 트리

알고리즘

- 유니온-파인드를 통해 문제를 수행한다.

- 간선들의 가중치를 기준으로 정렬하여 최소 스패닝 트리의 가중치를 구한다.

- 반복문을 통해 두 간선들의 두 정점을 유니온-파인드를 통해 확인한다.

- 두 정점의 부모 노드가 같지 않다면 스패닝 트리인 것이다.

- 부모 노드가 같지 않은 두 정점을 작은 루트 노드를 기준으로 합친다.

코드

import sys

# 최소 스패닝 트리
# 유니온 파인드


# 부모 노드 찾기
def find(a):
    if a == parent[a]:
        return a

    parent[a] = find(parent[a])

    return parent[a]


# 트리 합치기
def union(a, b):
    a = find(a)
    b = find(b)

    # 작은 루트 노드를 기준으로 합침
    if b < a:
        parent[a] = b
    else:
        parent[b] = a


v, e = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(e)]
graph.sort(key=lambda x: x[2]) # 간선들을 가중치 기준으로 정렬시킨다.
parent = [i for i in range(v+1)]
answer = 0

# 반복문을 통해 간선들의 두 정점을 확인
for s, e, w in graph:
    # 부모 노드가 같지 않다면 스패닝 트리!
    if find(s) != find(e):
        union(s, e) # 두 노드를 합친다.
        answer += w

print(answer)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법