[대표 유형] 최소 신장 트리(Minimum Spanning Tree)

문제 설명

정점의 개수 n, 양방향 간선 정보가 담긴 edges가 매개 변수로 주어질 때 최소 신장 트리의 가중치 총합을 반환하는 solution 함수를 작성하시오.

그래프는 연결그래프(임의의 두 정점 사이에 경로가 존재하는 그래프)만 주어진다고 가정합니다.
그래프는 항상 최소 신장 트리가 존재하는 경우만 주어진다고 가정합니다.

개념 설명

최소 신장 트리(Minimum Spanning Tree)는 주어진 양방향 그래프에 대하여 간선의 가중치 총합이 최소인 신장 트리를 의미합니다.

최소 신장 트리에 대해 이해하기 위해서는 '신장 트리(Spanning Tree)'를 먼저 이해해야 합니다. 신장 트리는 주어진 양방향 그래프에서 모든 정점을 포함하는 트리 형태의 부분 그래프를 의미합니다.

다음과 같은 양방향 그래프가 주어졌다고 가정합니다.

이때 주어진 그래프에서 다음과 같은 부분 그래프를 고려할 수 있지만 첫 번째 부분 그래프는 트리가 아니고, 두 번째 부분 그래프는 모든 정점이 포함되어 있지 않기 때문에 신장 트리가 아닙니다.

해당 그래프에서 신장 트리의 예시로는 다음과 같습니다.

그 중에서 간선의 가중치를 모두 더했을 때 첫 번째 신장 트리 간선의 가중치 총합(트리의 크기)은 24이고, 두 번째 신장 트리의 경우에는 17입니다.
다른 모든 신장트리를 고려하더라도 트리의 크기의 최솟값은 17이며, 따라서 두 번째 신장 트리는 최소 신장 트리입니다.
일반적으로 주어진 그래프에서 간선 가중치 총합(크기)이 최소인 신장 트리는 여러 종류가 가능합니다.

제한 사항

• 정점의 개수 n은 2 이상 10,000 이하의 자연수입니다.
• 양방향 간선 정보 edges의 원소는 특정 간선의 양 끝 정점 x, y와 간선의 가중치 w로 이루어집니다.
  • x, y는 1 이상 n 이하의 자연수입니다.
  • w는 10,000 이하의 자연수입니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 위의 설명에서 예시로 제시된 그래프와 동일합니다.

2번 테스트케이스 설명

• 주어진 그래프는 트리이며 자기 자신이 해당 그래프의 최소 신장 트리가 됩니다. 이때 모든 간선 가중치의 총합은 19입니다.