MST1 [C/C++] 백준 #2887 행성 터널(크루스칼 알고리즘) 이번 문제는 크루스칼 알고리즘을 이용해서 풀었습니다. https://www.acmicpc.net/problem/2887 하지만, V개의 행성을 모두 연결한다면, \(V(V-1)\)만큼의 간선이 생기므로, 정렬을 할 때, 주어진 V값에 대해서 느려질 수 있습니다.간선의 갯수는 최소 비용 신장 트리(Minimum Spanning Tree)를 프림 알고리즘을 이용하든, 크루스칼 알고리즘을 이용하든 모두 시간 복잡도가 주어진 V값의 최대치라면, 시간초과가 됩니다. \(E = V(V-1)\)이 된다면, 프림 알고리즘 상에서는 \(O(E \log V) = O(V^2 \log V)\), 크루스칼 알고리즘 상에서는 \(O(E \log E) = O(V^2 \log V\) 형태가 되겠죠. 물론 프림 알고리즘을 구현할 .. 2024. 8. 25. 이전 1 다음
