✓

태그:

29. 최소 신장 트리 CLASS 5 ESSENTIAL

크루스칼? 프림? 그게 뭐죠…??

풀이 비스무리한거 보기

주어진 그래프의 최소 스패닝 트리를 구하는 문제입니다. 최소 스패닝 트리를 구하는 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있는데, 저는 크루스칼로 풀었습니다. 크루스칼 알고리즘은 모든 노드에 대해 각 노드가 루트인 트리 V개를 만들어놓고(트리의 집합, 즉 숲을 만든다고 합니다), 가중치가 작은 간선부터 차례대로 탐색하여 간선을 숲에 추가했을 때 두 독립적인 트리가 합쳐지는지 체크하여 그렇다면 추가, 아니면 버립니다. 이 과정을 모든 간선에 대해 적용하면 최소 스패닝 트리에 속하는 간선을 제외하고는 모두 버려집니다. 남은 간선의 합을 구하면 문제의 답이 됩니다.

두 독립적인 트리가 합쳐지는지 체크하는 방법은 분리 집합 구조를 사용하는 방법입니다. 분리 집합을 트리를 대신하여 사용할 수 있습니다. 분리 집합을 사용하면 원소쌍에 대해 이미 이어진 상태인지, 또는 독립적인 상태인지 확인할 수 있습니다. 이를 통해 간선의 양 정점이 이미 연결된 상태인지 확인하여 간선을 추가할지 말지 결정할 수 있습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-03-05 12:07:24

---