크루스칼 (Kruskal)

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 입니다. 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이죠. 보통 여러 개의 도시가 있을 때, 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하는 문제에서 적용됩니다.

 

크루스칼 알고리즘에서는 간선 리스트를 많이 이용합니다. 아래와 같이 방향이 있는 그래프에서는 출발, 도착 지점을 기록하고 비용이 있는 경우 추가적으로 기록해줍니다. 만약 방향이 없는 그래프라면 출발과 도착의 순서는 상관이 없습니다.

 

그럼 크루스칼을 한 번 구현해볼까요?

크루스칼을 구현하기 위한 단계를 간단하게 정리해보았습니다.

 

 

Step 1. 비용이 적은 순서대로 간선 리스트를 정렬해줍니다.

 

Step 2. 가장 위의 간선(비용이 가장 적은 간선)부터 이어나가며 비용을 계산합니다. 단, 싸이클이 형성되는 간선은 잇지 않습니다.

이때 싸이클의 여부는 Union-Find로 알 수 있습니다. 두 노드의 루트 노드가 같을 경우, 같은 싸이클 안에 존재 한다는 소리이기 때문입니다.

 

생각보다 간단하죠?

크루스칼의 시간 복잡도는 정확하게는 N logN + 1 + N 이지만, O(N logN) 정도로 알고 계시면 됩니다 :)

 

---

 

이번에도 예제 하나를 살펴보고 끝내볼까요?

아래 예제는 백준 1922번 - 네트워크 연결 입니다. (swift 구현)

 

 

정말 위에서 다룬 정석적인 크루스칼을 구현하면 됩니다.

노드의 개수 N과 간선의 개수 M을 받고, M개의 간선 정보를 받아 간선 리스트에 저장합니다.

그리고 위에서 다뤘던 크루스칼 구현 단계 그대로 행해주면 되죠.