Kruscal 알고리즘

개념

스패닝 트리 (간선의 수 최소. 사이클이 생기면 안됨). 를 만드는 알고리즘

그리디 알고리즘. 

길이(가중치)가 가장 작은 간선부터 연결함. 근데 그러다 보면 사이클이 생길 수 있음.

사이클을 피하는 알고리즘 필요.

 방법 : 사이클 피하기

간선이 연결된 노드들을 그룹으로 묶고 같은 그룹끼리 연결하는 간선은 피하는 것, Disjoint Set을 활용함.

 

1. 우선 간선후보들을 가중치 순으로 정렬함
2. 간선 후보목록을 순회하며 가중치가 가장 작은 간선후보부터 사이클 검사를 함(Disjoint Set을 사용해 간선에 연결된 두 정점이 같은 팀인지 확인함). 참고 DisjointSet: https://ddukddaksudal.tistory.com/54
3. 같은 팀이면 다음 간선 후보로 넘기고 다른 팀이면 간선을 추가함(연결함).

 

활용 : 미로 만들기 알고리즘.

크루스칼 알고리즘을 활용해 미로를 만들어보자.

우선 체스판 같은 형태의 지도를 생각해보자.

여기서 검정색 칸은 벽이 아닌 곳, 흰색 칸은 벽이라고 생각해보자. 

이 때 맨 왼쪽 위에서 출발해 맨 오른쪽 아래로 도착하는 미로를 만들어보자.

우선 벽이 아닌 곳들을 벽을 뚫어서 이어주어야 한다. 다시 말하면 정점들을 간선으로 이어주어야 한다. 

즉 검정 칸은 정점, 흰색 칸은 간선후보이다. 

여기서 크루스칼 알고리즘을 적용하려면 간선 후보들에는 가중치가 있어야 한다. 가중치는 각 간선 후보마다 랜덤한 값으로 설정해주자.

그럼 크루스칼 알고리즘을 적용할 준비가 끝났다.

 

간선 후보들(흰색 칸들)에 대해 크루스칼 알고리즘을 적용하면 랜덤하게 길이 뚫리고, 빙빙 도는 순환구조(사이클) 도 없으며, 무조건 모든 검정 칸들이 이어져있는, 즉 출발점과 도착점이 이어져있는 예쁜 미로가 만들어질 것이다.