반응형 최소 스패닝 트리1 [C/C++] 백준 #1647 도시 분할 계획(크루스칼 알고리즘) 이번 문제는 전형적인 최소 스패닝 트리(Minimum Spanning Tree) 문제입니다. 최소 스패닝 트리를 구하는 방법중 대표적인 방법은 프림(Prim) 알고리즘과 크루스칼(Kruskal) 알고리즘이 있습니다. 둘 중에 어떤 알고리즘이 좋은가를 할 때에는 제 개인적으로는 크루스칼 알고리즘이 더 좋습니다. 알고리즘 효율은 프림 알고리즘은 \(O(E \log E)\)이고 크루스칼 알고리즘은 \(O(E \log E)\) 로 비슷합니다. 물론 우선순위큐를 잘 만들면 프림 알고리즘은 \(O(E \log V)\) 까지도 가능하지만, 사실상 의미가 없습니다. \(E\) 자체의 최대치가 \(V(V-1)/2\) 이므로 로그(log) 함수 안에서는 아무런 의미가 없습니다. 개인적으로 크루스칼 알고리즘을 더 선호하는 .. 2022. 9. 20. 이전 1 다음 728x90
