문제 요약

그래프의 최소 스패닝 트리를 구하라

최소 스패닝 트리란

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

신장 트리랑 스패닝 엥 뭐가 다르지??

같음ㅎ... 영어싫다
신장 = spanning

최소신장트리 자세히 정리된 티스토리

MST의 구현방법으로 크루스칼 알고리즘, 프림 알고리즘을 쓰는 것이다!

👊 문제를 보고 든 생각

어 그러나 저러나 크루스칼로 최소신장트리를 구하면 되겠구만
크루스칼 코드 재활용해야겠다

🗡 첫번째 시도

# 특정 원소가 속한 집합 찾기 
def find_parent(parent, x) :
	# 루트노드가 아니라면, 루트노드를 찾을때까지 재귀호출
  if parent[x] != x :
    parent[x] = find_parent(parent, parent[x])
  return parent[x]

        
# 두 원소가 속한 집합 합치기
def union_parent(parent, a, b) :
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  
  if a < b :
    parent[b] = a
  else :
    parent[a] = b

# 노드의 갯수와 간선(union 연산)의 갯수 입력받기
v, e = map(int, input().split())
parent = [0] * (v+1) #부모 테이블 초기화


# 모든 간선을 담을 리스트와 최종 비용을 담을 변수 
edges = []
result = 0

# 부모 테이블상에서, 부모를 자기자신으로 초기화
for i in range(1, v+1) :
	parent[i] = i

# 모든 간선에 대한 정보를 입력받기
for _ in range(e) :
  a, b, cost = map(int, input().split())
  # 비용순으로 정렬하기 위해서 튜플의 첫번째 원소를 비용으로 설정
  edges.append((cost, a, b))

# 간선을 비용순으로 정렬
edges.sort()

# 간선을 하나씩 확인하며
for edge in edges :
  cost, a, b = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함
  if find_parent(parent, a) != find_parent(parent, b) :
    union_parent(parent, a, b)
    result += cost
 
print(result) # 최종 최소 비용을 출력

통과👻!!