[백준] 최소신장트리 (MST) - 최소 스패닝 트리

지난번 최소신장트리의 개념을 공부했다.
최소한의 개념만으로 풀어 볼 수 있는 문제가 바로 아래 링크의 문제이다.
https://www.acmicpc.net/problem/1197

최소신장트리는 노드 , 간선 , 간선의 가중치가 주어지는 상황에서 최소한 간선의 가중치를 유지하며 모든 노드가 하나의 그래프에 속해있는 상태를 말한다.

위 설명을 봤을때 딱 기억나는것이 한가지 있다. 바로 유니온 파인드..
유니온 파인드를 이용하면 MST를 구성할 수 있다.
유니온 파인드의 사이클을 점검하는 TASK, 같은 그래프에 속하는지 보는 TASK가 명확히 들어 맞는다.

물론 유니온 파인드만 사용하면 풀순없지만 +@를 통해 쉽게 해결할 수있다.

MST의 목표는 "최소의 간선 가중치"이다. 두 노드와 간선, 가중치가 주어질 것인데 이때 가장 중요한게 가중치다.

그럼 어떻게 간선의 합을 최소한으로 만들 수 있을까??
쉽게 생각해보면.. 가장 가중치가 낮은 간선만 연결을 하면 되는데, 막 연결 할 수 없으니. 유니온파인드를 이용해 이미 같은 그래프가 아닐때 연결하면된다!

정리
1.Value값으로 오름차순 정렬한다.
2. 두 노드가 같은 그래프인지 확인한다.(root가 같은지 확인)
3. 연결이 안되어있다면 연결한다.
4. 가중치 값을 더한다.

위와 같은 알고리즘을 따르게 된다. 물론 MST의 총 간선은 N-1이므로 4. 가중치 값을 더할때 N-1번 만큼만 수행하면 끝이다!

import sys

input = sys.stdin.readline
sys.setrecursionlimit(1000000)
V, E = map(int,input().strip().split(" "))

node = [x for x in range(V + 1 )]
root = [x for x in range(V + 1 )]

edge_list = []

for _ in range(E):
  edge_list.append(list(map(int,input().strip().split(" "))))

edge_list = sorted(edge_list, key = lambda x : (x[2] , x[0]))

def getParent(parent, n):
  if parent[n] == n: 
    return n
  parent[n] = getParent(parent, parent[n])
  return parent[n]

def union(parent , n1 ,n2 ):
  pn1 = getParent(parent, n1 )
  pn2 = getParent(parent, n2 )

  if pn1 <= pn2 : # pn2 가 병합되야함
    parent[pn2] = pn1
  else:
    parent[pn1] = pn2
  
def fine( parent , n1 , n2):
  if getParent(parent, n1) == getParent(parent, n2):
    return True
  else:
    return False


result = 0
for i in edge_list:
  s , e , v = i

  if fine(root , s , e ):
    continue

  union(root, s, e)
  result += v

  
print(result)