[Leetcode] 1584. Min Cost to Connect All Points

문제 : https://leetcode.com/problems/min-cost-to-connect-all-points/

---

최소신장트리, MST를 만드는 문제이다.

크루스칼 알고리즘을 사용했다.

각 point들을 정점으로 보고 모든 정점들간 간선을 연결하며 간선의 cost는 맨해튼 거리 수식으로 계산한다.

간선들을 cost 오름차순으로 정렬한뒤 DSU를 사용하여 사이클이 발생하는지 체크한다. 사이클이 발생하면 간선을 사용하지 못하고 사이클이 발생하지 않으면 cost를 정답변수에 더해준다.

 

시간복잡도는 정점의 수가 points 배열 크기이고 간선 수가 points^2이므로 간선들을 오름차순 정렬하는데 드는 O(간선 * log간선)이 된다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1584.%20Min%20Cost%20to%20Connect%20All%20Points.cpp