본문 바로가기
알고리즘/백준

[백준][트리] 1197 최소 스패닝 트리(크루스칼 알고리즘)

by hs_seo 2017. 7. 6.

이 문제는 최소 스패닝 트리를 구현하는 방법중 크루스칼 알고리즘을 이용하여 구현하면 된다. 


크루스칼 알고리즘은 그래프 사이 연결의 최소비용을 찾으면 된다. 

간선을 비용순으로 정렬하고,

가장작은 비용이 들어가는 간선을 사이클이 생기지 않는 순서대로 선택하면된다. 


간선 사이의 사이클은 union, find 연산을 이용하여 처리한다. 






반응형