[알고리즘] Kruskal Algorithm, Union Find (크루스칼 알고리즘, 유니온 파인드)

오늘은 크루스칼(Kruskal) 알고리즘과

이를 구현하기 위해 필요한 개념인 Union Find에 대해 알아보겠습니다. 

 

우선 이를 이해하기 위해서는 Minimum Spanning Tree에 대한 이해가 필요합니다.

Minimum Spanning Tree (최소 신장 트리)와 크루스칼 알고리즘에 대해서는

지난 포스팅에서 상세하게 설명했으니 참고 바랍니다. 

 

 

---

 

Kruskal Algorithm

: 크루스칼 알고리즘

: 음수 가중치가 없는 무방향 그래프에서 Minimum Spanning Tree를 찾는 알고리즘

 

그런데, Minimum Spanning Tree를 찾을 때에는 사이클이 발생하면 안된다고 했습니다.

그럼 사이클이 발생했는지는 어떻게 알 수 있을까요?

 

사이클이 발생하는 경우는

같은 그래프에 속한 두 노드를 연결했을 때 입니다. 

 

그리고 내가 고른 두 노드가 같은 그래프에 속하는지 아닌지는,

바로 Union Find의 개념을 이용해서 판별할 수 있습니다. 

 

Union Find

: 합집합 찾기

: Disjoint-Set 알고리즘

 

말 그대로, 어떤 두 임의의 원소를 선택했을 때 

그 두 원소가 같은 집합에 속하는지 판별하는 방법입니다. 

 

그래프에서 생각해보자면,

어떤 두 임의의 노드가 같은 그래프에 속하는지 판별하는 방법이라고 할 수 있겠네요. 

 

 

위의 경우 2개의 그래프가 존재합니다.

이 때, 노드 2, 4가 같은 그래프에 있는지를 확인하고 싶습니다. 

그러면 우리는 2로부터 0 → 3 → 4 의 과정을 거쳐 2와 4가 연결되어 있음을 확인할 것입니다.

 

이 과정은 상당히 귀찮고 비효율적입니다. 

만약 2와 4사이에 1억개의 노드가 있다면 더더욱이요..

 

 

그래서 위와 같이 나타내기로 합니다.

각 집합의 대표자(부모)를 정해 멤버들이 그 대표자를 가리키도록 합니다. 

이렇게 하면 같은 부모를 가진 노드들은 같은 그룹에 속한다는 것을 알 수 있습니다.

 

또한 대표자가 2명 존재하므로, 그래프는 총 2개라는 사실도 알 수 있게 되죠. 

그리고 보통 그래프 내에서 가장 작은 값을 가진 노드를 부모로 채택하게 됩니다. 

 

 

 

예시 그래프에서 Union Find의 동작 과정을 살펴보면 다음과 같습니다. 

 

 

 

각 노드들의 부모를 저장할 공간을 만들어, 처음에는 부모를 자기 자신으로 초기화합니다. 

 

 

 

그리고 0과 1은 연결되어 있으므로, 부모를 Union 할 수 있습니다.

앞서 말했듯이, 통상적으로 값이 작은 노드를 부모로 채택하기 때문에

1의 부모를 0으로 바꿔줍니다. 

 

 

 

위와 같은 이유로 2와 3의 부모 또한 0으로 바꿀 수 있습니다.

 

그렇다면 4는 어떨까요?

4는 3과 연결되어 있기 때문에 4의 부모는 3이 될 수 있습니다.

 

그런데 3의 노드를 확인해봤더니 3의 부모가 자기 자신이 아닙니다.

즉, 3이 다른 노드를 부모로 가리키고 있습니다.

 

이 경우 3의 부모 노드인 0으로 가서 다시 확인합니다. 

0의 노드를 확인해봤더니 부모가 자기 자신입니다.

즉, 해당 노드가 대표자(부모)입니다.

 

그러므로 4의 부모는 최종적으로 0이 됩니다. 

 

즉 Union Find에서 부모 노드를 갱신할 때,

자기 자신을 부모로 가지는 노드를 찾을 때 까지 깊이 탐색을 하게 됩니다.

 

 

이 과정까지 마치면 위의 그림과 같이 하나의 집합을 이루게 됩니다.  

 

 

나머지 노드들도 같은 과정을 통해 부모를 갱신할 수 있습니다.

이렇게 같은 부모를 가지는 노드들을 하나의 집합으로 묶을 수 있게 되었습니다. 

 

Kruskal Algorithm 구현 

Union Find를 통해 임의의 두 노드가 같은 그래프에 속하는지 아닌지를 알 수 있게 되었습니다. 

 

그리고 앞서 말했듯이, 사이클은 같은 그래프에 속한 두 노드를 연결했을 때 발생합니다. 

 

따라서 크루스칼 알고리즘에서는 간선을 선택하기 전에 해당 간선이 연결하는 두 노드의 부모를 확인해부모가 서로 같다면(같은 그래프에 속한다면) 그 간선은 선택하지 않습니다. 

 

Union Find를 이용해 Kruskal 알고리즘을 구현한 코드는 

예제와 해설을 통해 설명하도록 하겠습니다.

 

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

[프로그래머스] 섬 연결하기 (JAVA)