BOJ 1922 네트워크 연결

문제

접근 방법

모든 컴퓨터를 연결하면서 그 연결하는 간선들의 가중치의 합을 최소로 해야 하기 때문에 Minimum Spanning Tree를 생각했다.

MST 알고리즘 중 제일 직관적인 크루스칼 알고리즘을 사용하기로 하였다.

간선들을 정렬하고 가장 weight가 작은 애부터 spanning tree에 추가하면서 cycle을 형성한다면 (비효율적인 spanning tree) 그 간선은 사용하지 않는다.

이때, cycle을 형성하는지 판별하기 위해 union-find 알고리즘을 써야한다는 것이 중요했다.

정답 코드

import sys
input = sys.stdin.readline

"""
모든 정점들을 최소한의 weight로 연결해야 하므로 MST를 구하는 문제임을 알 수 있다.

"""

n = int(input())
m = int(input())


edges = []
for _ in range(m):
  a,b,c = map(int, input().split())
  edges.append((a,b,c))

#가중치를 기준으로 오름차순으로 정렬
edges.sort(key=lambda x: x[2])

parents = [i for i in range(n+1)]

total_min = 0

def find(a):
  if parents[a] == a:
    return a
  else:
    return find(parents[a])

  
def union(a,b):
  parent_a = find(a)
  parent_b = find(b)
  #사이클 형성한다면
  if parent_a == parent_b:
    return 0

  #사이클 형성하지 않는다면 부모 update
  else:
    if parent_a > parent_b:
      parents[parent_a] = parent_b
    else:
      parents[parent_b] = parent_a
    return c
    
total_min = 0

for a,b,c in edges:
  #cycle을 형성하지 않는 간선들만 최종 가중치에 더함
  total_min += union(a,b)

print(total_min)