[Programmers] 섬 연결하기

문제 : https://programmers.co.kr/learn/courses/30/lessons/42861

---

오랜만에 푸는 최소신장트리문제~

크루스칼 알고리즘으로 풀었다.

먼저 cost 오름차순으로 costs 배열을 정렬한다.

costs 배열을 탐색하면서 Union-Find로 해당 간선을 연결하면 사이클이 생기는지 확인한다.

만일 두 정점의 부모노드가 같다면 연결하면 사이클이 생기기 때문에 해당 간선을 선택하지 않는다.

두 정점의 부모노드가 다르면 해당 간선을 연결해도 사이클이 생기지 않기 때문에 해당 간선을 선택하고 해당 간선의 비용을 정답에 더해준다.

 

시간복잡도는 간선들을 오름차순 정렬하는데 드는 시간인 O(ElogE)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/Greedy/%EC%84%AC%20%EC%97%B0%EA%B2%B0%ED%95%98%EA%B8%B0.cpp