tose33

최소 스패닝 트리, 크루스칼 알고리즘에 대한 설명은 이미 쓴 글이 있으니 이로 대체한다. https://tose33.tistory.com/485 최소 신장 트리(MST), 크루스칼 알고리즘 (kruskal) 학교에서 배웠었는데 알고리즘 문제에 필요해서 다시 한번 정리. Union-Find 알고리즘 : (https://tose33.tistory.com/614) - 크루스칼 알고리즘 최소의 비용으로 모든 노드를 연결하는 알고리즘 - 신장 트리 tose33.tistory.com 크루스칼 알고리즘의 흐름은 다음과 같다 가중치를 기준으로 간선을 오름차순 정렬한다 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가한다 사이클을 형성하는 간선은 추가하지 않는다 간선의 갯수가 정점의 수보다 1개 적을때 MST는 완성..

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 최소 신장 트리(MST) 찾는 크루스칼 알고리즘 : (https://tose33.tistory.com/485) 크루스칼 알고리즘으로 최소 신장 트리의 가중치를 찾는 문제.