kruskal's algorithm
-
(백준 1647번 도시 분할 계획) (라이님 블로그 대회 알고리즘 따라잡기 19) 최소 스패닝 트리(Minimum Spanning Tree) 크루스칼 알고리즘(Kruskal's algorithm)PROGRAMMING/알고리즘 2024. 6. 17. 10:32
최단 거리 찾는 알고리즘 3인방을 끝내고 오늘은 최소 스패닝 트리를 구하는 알고리즘에 대해 알아보았다. 라이님 블로그에 나온 알고리즘은 바로 크루스칼 알고리즘! 정렬 + 유니온 파인드를 이용하면 시간복잡도 O(ElogE)로 구할 수 있다! gpt에게 살짝 수정시킨 알고리즘은 다음과 같다. #include #include #include using namespace std;struct Edge { int u, v, w; bool operator edges; edges.reserve(M); // 메모리 할당 최적화 for (int i = 0; i 위 풀이를 기준으로 1647번을 풀어보았다. 백준 1647번https://www.acmicpc.net/problem/1647 MST를 먼저..