내가보려고만든 메자노트

최소 스패닝 트리 2가지 알고리즘 내용 문제 보러 가기 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 이 문제는 최소 스패닝 트리의 가장 기본적인 구현을 다루는 문제이다. 최소 스패닝 트리는 스패닝 트리 중(그래프 내의 모든 정점을 포함하는 트리) 연결된 간선 가중치가 가장 작은 것들로 구성된 트리를 의미한다. 모든 정점을 포함하기 위해서는 하나의 트리로 연결돼야 하는데 이때 사용하는 알고리즘이 크루스칼, 프림 2가지의 방법이 있다. 이 중 크루스칼을 이용하여 풀이하였다. 문제풀이 크루스칼 알고리즘은 Union-Find를 사용하여 구현할 수 있다. -> Union-Find 설명 - 간선의 정보를 ..