그래프 이론

[baekjoon 1922] 네트워크 연결 - 최소 스패닝 트리(크루스칼, Union-Find)

www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 최소 스패닝 트리를 만들어서 간선들의 합이 최소가 되게끔 풀면 된다. 쓰인 알고리즘은 크루스칼 알고리즘과 Union-Find 알고리즘이다. 크루스칼 알고리즘을 통해 모든 Vertex를 최소의 비용으로 연결을 시키면 되고, 연결 하는 도중 싸이클이 생기지 않도록 Union-Find 알고리즘을 사용하면 된다. - 최소 스패닝 트리란? : 우선 스패닝 트리란 트리의 모든 노드를 포함하고, 노드끼리 연결이 되어있으며 싸이클이 발생하지 않는 트리다. : 여기에 최소의 뜻을 더하면 노드끼리 연결하되, 최소의 비..