Kruskal Algorithm 크루스칼 알고리즘 ?!

Kruskal Algorithm

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다

다시 말해 최소비용 신장트리를 만들기 위한 대표적인 알고리즘 !

 

프로그래머스 섬 연결하기 문제를 풀다가 개념을 정리한다

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

코딩테스트 연습 - 섬 연결하기

---

노드와 간선

노드 = 정점 = 도시 를 의미하며 동그라미에 해당하는 부분이고

간선 = 거리 = 비용 을 의미하며 선에 해당하는 부분이다

 

예시로 살펴보면 아래 그래프는 노드가 4개 간선이 5개 이다

프로그래머스 섬 연결하기 문제 예시

---

핵심개념

노드 7개와 간선 11개를 가진 그래프

간선을 거리가 짧은 순서대로 그래프에 포함시킨다 !

 

일단 모든 노드를 최대한 적은 비용으로 연결만 시키면 되기 때문에

간선 정보를 오름차순으로 정렬한 후 비용이 적은 간선부터 그래프에 포함시키면 된다

포함시키전 사이클 테이블을 확인한 후 포함해야한다

 

사이클은 그래프가 서로 연결되어 사이클을 형성하는 경우를 의미한다

최소 비용 신장 트리에서는 사이클이 발생하면 안된다

 

이는 Union-Find ( 합집합 찾기 ) 를 공부하면 이해가 쉽다

---

Union-Find Algorithm

앞선 그래프에 크루스칼 알고리즘을 이용해 최소 비용을 구한 결과

초기에 모든 값이 자기 자신을 가리키도록 만들고 

이후 첫 행에 노드의 번호를 두 번째 행에는 부모의 노드 번호를 적는다

이는 자기 자신이 어떤 부모에 포함되어 있는지를 의미하게 된다

 

하지만 한 번에 연결성을 파악할 수 없기 때문에 이를 해결하기 위해 재귀 함수가 사용된다

부모를 합칠때는 일반적으로 더 작은 값의 쪽으로 합치게 된다 ( Union )

 

Find 알고리즘은 두 개의 노드의 부모 노드를 확인하여

현재 같은 집합에 속하는지 확인하는 알고리즘이다

---

참고

https://youtu.be/AMByrd53PHM

https://youtu.be/LQ3JHknGy8c