별자리 만들기
-
(백준 4386번 별자리 만들기) (라이님 블로그 대회 알고리즘 따라잡기 19) 최소 스패닝 트리(Minimum Spanning Tree) 크루스칼 알고리즘(Kruskal's algorithm)PROGRAMMING/알고리즘 2024. 6. 18. 11:22
백준 4386번https://www.acmicpc.net/problem/4386 처음에는 스패닝 트리 문제라는 생각이 안 드는 문제.. n개의 별들을 잇는 최소의 거리를 찾는 문제다. n개의 별들 사이의 거리는 주어져 있지 않으므로 $\frac{n \times (n-1)}{2}$의 간선에 대해 길이를 먼저 구해야 한다. 이 중 거리가 최소인 간선부터 이어(일종의 그리디 알고리즘) 최소의 간선 갯수만 이으면 된다. V개의 노드가 있다면 V-1개의 간선을 잇는 것이 최소이기 때문에 자연스럽게 트리 모양이 된다는 것을 알 수 있다. 즉, 가중치의 합이 최소인 트리를 찾는 MST 문제가 되는 것이다! 참고로 double을 사용할 때 %lf를 쓴다는 사실과 소수점 두번째 자리까지만 프린트하는 %.2lf를 까먹어..