넘치게 채우기

https://www.acmicpc.net/problem/1197BOJ - 최소 스패닝 트리문제 유형: 최소 신장 트리, 최단 경로문제 난이도: Gold IV시간 제한: 1초메모리 제한: 128MB 문제그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 ..

최소 신장 트리 (Minimum Spanning Tree, MST) 신장 트리는 그래프의 모든 정점을 연결하는 트리를 말한다. (사이클이 생기지 않음) 최소 신장 트리는 그래프의 모든 정점을 연결하는 간선들의 가중치의 합이 최소인 트리를 말한다. (신장 트리중 가장 저렴한 비용) 크루스칼 알고리즘(Kruscal's Algorithm) 크루스칼 알고리즘은 최소 신장 트리를 찾는 방법 중 하나이다. 1. 모든 간선들을 가중치 기준으로 오름차순 정렬한다. 2. 가장 작은 가중치의 간선부터 선택한다. 3. 고른 간선이 사이클을 형성한다면, 선택하지 않는다. 4. 2와3을 계속 반복한다. 아래는 크루스칼 알고리즘의 예시이다. 우선, 간선들의 가중치를 기준으로 오름차순 정렬해준다. A-B : 1 A-C : 2 B-..