문제

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

Input)
3 3
1 2 1
2 3 2
1 3 3
Output)
3

Point

이미 경로가 있는 두 정점의 간선을 추가하면 Cycle이 생긴다.

• 한 tree안 두 정점의 간선을 추가하면 안 된다.

tree단위로 정점을 관리하는 법

• 각 tree의 첫 노드를 최상위 조상 노드로 설정. 새로운 간선을 추가 할 때 두 노드의 각자 조상노드를 비교한다.
• 조상노드가 같으면 같은 tree에 속해있어서 간선 이으면 안된다. 조상 노드가 다르면 다른 tree에 속해있어서 간선이어도 된다.
• 구현
  • 각 정점의 parent를 저장하는 배열생성
    : 초기값 = 자기자신번호
  • find() 함수
    : 각 노드의 조상노드를 리턴
    : 호출 시 인자로 넣은 노드의 parent를 조상노드로 설정
    -> tree의 차수를 줄이는 역할
  • union() 함수
    : 두 노드가 다른 tree에 있는지 확인. (조상 노드가 다른지 확인)
    : 다른 tree에 있으면 두 tree 합친다.
    : 한 tree의 조상노드의 parent를 다른 tree의 조상노드로 설정

pq(heap)를 활용하여 가중치가 작은 간선부터 추가

• 간선 추가가 되면 : union의 return이 True
  -> count++, 가중치++
  

전체코드

import heapq

v, e = [int(x) for x in input().split()]

par = [x for x in range(v+1)]
pq = []

for i in range(e):
    a, b, c = [int(x) for x in input().split()]
    heapq.heappush(pq, (c, a, b))

def find(x):
  if par[x]==x:
    return x
  grand = find(par[x])
  par[x] = grand
  return grand
  
def union(x,y):
  tree_x = find(x)
  tree_y = find(y)
  if tree_x == tree_y:
    return False
  par[tree_y] = tree_x
  return True

count = 0
val = 0
while True:
    c, a, b = heapq.heappop(pq)
    if union(a,b):
      count += 1
      val += c
    if count == v-1:
      break

print(val)