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

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

1197번: 최소 스패닝 트리

 

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

 

풀이

 

이 문제는 최소 스패닝 트리 관련한 풀이로 처음 각 지점의 값을 자기자신으로 지정한 뒤 위치를 거치면서

해당위치를 업데이트를 하는 것이다.

 

업데이트를 하기 위해서 가중치를 오름차순으로 탐샐을 진행한다. 이렇게 하는것이 최소의 비용을 들여서 모두 연결된

 

트리를 만들 수 있기 때문이다.

 

# git commit -m "submit : BOJ 01197 최소 스패닝 트리 (eonyong)"
import sys
input = sys.stdin.readline

# Kruskal Algorithm을 활용한 문제로 해당 알고리즘을 잘 몰라
# 다른 블로거님을 참고
# https://velog.io/@guri_coding/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8A%A4%ED%84%B0%EB%94%94-%EC%B5%9C%EC%86%8C%EC%8B%A0%EC%9E%A5%ED%8A%B8%EB%A6%ACMST-feat.-Python

# 이동 방향에 따라 parents애 도착 지점을 업데이트
def Union(s, e, parents):
    parents[max(s, e)] = min(s, e)
    return parents


# 만약, 도착지점이 자신과 같다면 그대로 반환, 아니면 계속 탐색하여 마지막 도착지를 반환
def Find(v):
    if v == parents[v]:
        return v
    return Find(parents[v])


answer = 0
n, m = map(int, input().split())

# 모든 간선을 저장하고 노드 간 가중치를 기준으로 오름차순 정렬을 한다.
# 모든 간선을 지나갈 수 있는 최소 거리이기 때문에, 가중치를 기준으로 하는 것이 낫기 때문
nodes = [list(map(int, input().split())) for _ in range(m)]
nodes.sort(key=lambda x: x[2])

# 각 간선의 도착지를 저정할 리스트를 만들어준다.
parents = list(range(n + 1))

# 각 간선 간 관계를 따라 탐색하면서, 가선의 도착지가 겹치지 않으면 다음 단계를 진행.
# parents 업데이트를 완료한 후 해당 가중치 w를 answer에 추가
for s, e, w in nodes:
    if Find(s) != Find(e):
        Union(Find(s), Find(e), parents)
        answer += w

print(answer)