최소 스패닝 트리1 [C/C++] 백준 1197: 최소 스패닝 트리 (Kruskal 알고리즘) https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 스패닝 트리는 크게 프림의 알고리즘과 크루스칼 알고리즘을 통해 구현이 가능하다. 이 문제에서는 크루스칼 알고리즘을 이용하여 최소 스패닝 문제를 해결했다! 크루스칼(Kruskal 알고리즘)? 크루스칼 알고리즘의 가장 기본적인 아이디어는 사이클이 만들어지지 않는 한에서 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가하는 것이다. .. 2023. 10. 10. 이전 1 다음
