MST (2) 썸네일형 리스트형 [알고리즘] 최소 스패닝 트리 최소 스패닝 트리 (Minimum Spanning Tree, MST)는 모든 정점을 연결하면서 가장 작은 가중치를 가지는 트리를 만드는 알고리즘이다. 트리를 만드는 알고리즘이므로 이 그래프는 사이클이 없는 DAG 형태여야 한다. 이 문제를 해결하는 데에는 두 가지 알고리즘이 대표적으로 사용되는데, 바로 크루스칼 알고리즘과 프림 알고리즘이다. 일단은 크루스칼 알고리즘을 설명한 뒤에 프림 알고리즘을 구현할 때가 되면 그때 와서 추가해 놓겠다.크루스칼 알고리즘 크루스칼 알고리즘은 모든 간선 중 가장 가중치가 작은 간선부터 차례로 연결시키는데, 만약 새로 연결하는 간선 때문에 사이클이 생긴다면 그 간선을 포기한다. 원리도 굉장히 간단하고 구현도 굉장히 간단하다. 근데 Greedy한 알고리즘 답게 증명은 간단하지.. [BOJ] 1922 네트워크 연결 문제: https://www.acmicpc.net/problem/1922 MST(최소 비용 신장 트리, Minimum Spanning Tree)를 찾는 문제로 정말로 naive하게 MST를 찾는 알고리즘을 구현해주면 된다. 나는 이 문제를 풀기 위해서 크루스칼 알고리즘을 사용했다. 지금 생각해 보니 좀 많이 이상하지만 정보올림피아드를 이제까지 준비하면서 단 한번도 MST를 사용하는 문제를 풀거나 코딩해 본적이 없었다. Union-Find (코드에서 DisJointSet)을 좀 쉽게 구현할 수 있게 되니까 비로소 알고리즘을 이해할 수 있었다. 난이도는 1.5/5 정도인 것 같고 코드는 아래와 같다.1234567891011121314151617181920212223242526272829303132333435.. 이전 1 다음