이 글에서는 크루스칼 알고리즘이 무엇인지에 대해서 알아보고, 이게 어떤 문제를 구현할 때 사용할 수 있는 알고리즘인지 어떻게 구현하는지 알아보도록 하자.
1. 크루스칼 알고리즘 ?? 언제 써먹어야 되는 알고리즘인가 ??
- 알고리즘 중에는, 여러가지 객체들 사이에 짝을 이루는 관계를 모델링 하기 위해서 사용되는 '그래프 알고리즘' 이라는 것이 있다.
이 그래프 알고리즘은 크게 Vertex라고 불리는 정점(Node)과, Edge라고 불리는 간선들의 조합으로 이루어져있다.
이 때, 방향이 없는 그래프에서 모든 노드를 포함하면서, 순환되는 경로를 제거한 형태를 '스패닝 트리(Spanning Tree)' 라고 한다.
이 스패닝 트리에서 가중치의 합을 최소로 만드는 스패닝 트리를 '최소 스패닝 트리(Minimal Spanning Tree)' 라고 한다.
우리는 이 '최소 스패닝 트리(MST)' 를 만들기 위한 방법으로 크루스칼 알고리즘을 사용하게 된다.
물론, 프림 알고리즘을 사용하는 방법도 있지만, 이 글에서는 크루스칼 알고리즘에 대해서만 알아보도록 하자 !
2. 크루스칼 알고리즘 동작(구현)원리 !
아마 위의 그림과 같이 표현될 것이다.
2 & 3. 위의 가중치값들 중 가장 작은 값을 선택한다. 아직 그 간선에 의해서 두 노드가 연결되어 있지 않다면
연결하기
B - C를 연결하는 '1'의 가중치가 가장 작은 값이다. 모든 간선들이 끊어져 있는 상태이고, B - C또한 연결되어 있지 않기
때문에 연결을 하고, B - C가 연결되었다고 표시한다.
현재까지의 과정을 그림으로 나타내면 다음과 같다.
간선의 최소값 찾기 반복 !
A - B를 연결하는 '3'의 가중치를 갖는 간선이 최소값인데, 아직 A - B는 연결되어 있지 않기 때문에, 연결해준다 !
이 후, D - E를 연결하는 간선도 연결, B - D를 연결하는 '4'의 가중치를 갖는 간선도 연결해준다. 여기까지의 과정을
그림으로 나타내면 아래와 같다.
그렇다면, 이 이후에 진행될 가중치가 '4'인 C - E 를 연결하는 간선을 보자. 노드 C와 E가 서로 연결되어 있지 않으면 연결
을 해줄 수 있지만, 연결이 되있다면 연결을 또 해주면 안된다. 왜냐하면 싸이클이 발생해버리기 때문이다.
그렇다면 위의 그림에서 C와 E가 연결되있는지 확인해보자.
C와 E는 (C → B → D → E) 루트를 통해서 이미 연결되어 있는 노드이다. 따라서, 연결을 하면 안된다 !
그렇다면 그 다음 값인 A와 D를 연결하는 가중치 '5'인 간선을 확인해보자. A와 D또한 (A → B → D) 로 이미 연결되어 있다.
따라서 연결을 하면 안된다 ! 그 이후에 나오는 A - E , C - D 간선도 이미 다 연결되어 있기 때문에 더 이상 연결하지 않고
끝내버린다. 즉, 위의 그림이 크루스칼 알고리즘으로 구현한 MST가 되는 것이다.
크루스칼이 진행되는 방식은 이렇다. 그렇다면 이제 실제 코드로 어떻게 구현해야 할지 구현방법에 대해서 알아보자.
3. 크루스칼 알고리즘 실제 코드로 구현하기 !
- 크루스칼 알고리즘을 실제 코드로 구현해보자. 먼저, 각 간선들의 가중치를 오름차순으로 정렬해주는 과정이 필요하다.
이 과정은 STL #include<algorithm>에서 제공하는 sort() 함수를 사용하면 쉽게 구현할 수 있다.
본인은 보통, 벡터에 3가지 값 < 가중치 , pair<노드1, 노드2> > 을 넣어서 관리해주면서, 가중치에 대해서 오름차순으로 정렬
하는 방식을 많이 사용한다.
- 지금부터 본격적으로 크루스칼 알고리즘이다. 위에서 정렬해놓은 가중치 값들 중에서, 가장 작은 가중치를 갖는 간선이
연결하는 두 노드가 연결되어 있는지 되어 있지 않은지 확인을 해주는 과정이 필요하다.
이 과정에서 많이 사용되는 방식이 union - find 방식이다. 이게 무슨 알고리즘이나 함수의 이름이 아니라, 그냥 이름을 붙혀
이렇게 흔히들 부르는 것이다.
union 이라는 것은 "합친다"는 의미를 가지고 있다. 즉, "두 노드가 연결되어 있지 않으면, 연결시킬테니, 두 노드를 합쳐라"
라는 의미이다.
그렇다면 우리는 실제 코드상에서, "합친다"를 표현할 수 있어야 한다. 이를 위해 1차원 배열을 하나 사용하게 된다.
흔히들 사용하는 이름이 'Parent[]' 라는 1차원 배열인데, 이 배열의 역할은 부모가 같은지 를 판단해 주는 배열이다.
즉, 서로 다른 두 노드가 같은 부모를 가지고 있다면 서로 연결되어 있음을 뜻하고, 서로 다른 부모를 가지고 있다면 서로
연결되어 있지 않음을 뜻한다.
이 배열의 초기값은 자기자신이 된다. 위에서 말했듯이, 처음에는 모든 노드가 서로 연결되어 있지 않은 상태로 시작을 해야
하므로, 예를 들어서 1~ 5번까지의 노드가 있다면 Parent[1] = 1, Parent[2] = 2 , ... , Parent[5] = 5 이런식으로 초기값을
가지게 된다.
find 라는 것은 "찾는다"는 의미를 가지고 있다. 여기서 찾는다는 것은 부모를 찾는다는 것을 의미한다. 위에서 부모가 같다면
서로 연결되어 있는 정점이라는 것을 의미한다고 했다. 즉, 서로 다른 두 노드의 부모를 찾아봤을 때, 그 두 개의 노드가 서로
같다면 더이상 연결할 필요가 없고, 서로 다르다면 서로 연결을 할 수 있는 것이다.
즉, 마지막으로 정리를 한번 해보자.
우리가 구현해야될 함수 내용으로는...
1. 서로 같은 부모를 갖는지 판단해주는 함수
2. 1번 과정을 위해서, 부모를 찾는 find 함수
3. 서로 다른 부모일 경우, 두 개의 노드를 연결해야 하므로, 합치는 union 함수
1. 서로 같은 부모를 갖는지 판단해주는 함수
bool SameParent(int x, int y) // 노드 x와 y가 서로 같은 부모를 갖는지 아닌지 판단해주는 함수
{
x = Find_Parent(x); // 노드 x의 부모 찾기
y = Find_Parent(y); // 노드 y의 부모 찾기
if(x == y) return true; // 두 부모가 같은 부모라면, true를 반환
else return false; // 두 부모가 서로 다른 부모라면, false를 반환
}
-------------------------------------------------------------------------------------------------
2. 1번 과정을 위해서, 부모를 찾는 find함수
int Find_Parent(int x) // 노드 x의 부모를 찾는 함수
{
if (Parent[x] == x) return x;
else return Parent[x] = Find_Parent(Parent[x]);
}
-------------------------------------------------------------------------------------------------
3. 서로 다른 부모일 경우, 두 개의 노드를 연결해주는 union 함수
void Union(int x, int y) // 노드 x와 y를 합쳐주는 함수
{
x = Find_Parent(x); // 먼저 x의 부모를 찾고
y = Find_Parent(y); // y의 부모를 찾아준다.
if (x != y) // 만약 두 노드의 부모가 서로 다르다면
{
Parent[y] = x; // 어느 한쪽 노드의 부모를 연결되는 다른 한쪽 노드로 설정해버림.
} // 이 과정을 통해 노드 x의 부모도 x, 노드 y의 부모도 x로 부모가 같아진다 !
}
지금까지 크루스칼 알고리즘에 대한 전체적인 개념과 풀이방법에 대해서 알아보았다.
알아두면 종종 써먹을 일이 많은 알고리즘이라서 알아두면 좋을 것 같다 !
위의 글은 본인이 엄청나게 공부를 깊게해서 전문적으로 써내려 간 글이 아닌, 본인이 이해한대로 최대한 쉽게 풀어써 내려간
글이니, 위의 글이 정답이다 ! 라는 마인드로 글을 읽지는 않았으면 좋겠다.
'[ Algorithm ] > # Solution - ' 카테고리의 다른 글
| [ 정렬 ] 선택 정렬 (Selection Sort) (C++) (0) | 2019.04.28 |
|---|---|
| [ 정렬 ] 버블정렬 (Bubble Sort) (C++) (0) | 2019.04.27 |
| [ 순열과 조합 구현 ] 재귀를 통한 구현(4 - 중복순열) (C++) (2) | 2019.01.31 |
| [ 순열과 조합 구현 ] 재귀를 통한 구현(3 - 중복조합) (C++) (2) | 2019.01.31 |
| [ 순열과 조합 구현 ] - 재귀를 통한 구현(2 - 순열) (C++) (7) | 2019.01.25 |