프림

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)에 대한 문제다. 더보기 최소 스패닝 트리란? 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 가중치의 합이 최소인 트리를 말한다. MST개념을 공부하면 가장 처음 접하게 되는 문제다. (골드 4지만 방법을 알면 실버급이라고 생각한다.) MST를 구하는 대표적인 방법으로는 크루스칼, 프림 2가지가 있다. 나는 이중에..
indeep
'프림' 태그의 글 목록