알고리즘 수업때 union-find라는 알고리즘을 처음 알게되어 이렇게 글로 정리를 해보았다.
수업시간에서 풀었던 문제정리 노션(친구찾기)
UNION-FIND(합집합 찾기)
union-find는 서로소 알고리즘이라고 불리기도 하는 대표적인 그래프 알고리즘이다. 여러개의 노드가 주어졌을때 그 중 두 노드를 선택해서, 현재 같은 그래프에 속해있는지 판별하는 알고리즘이다.
위 그림과 같이 연결되지 않은 여러개의 노드가 있다고 가정할때, 각각의 노드들은 자기 자신만을 집합의 원소로 가지고 있다.
이를 표로 나타내 보면 아래의 표와 같이 표현할 수 있다.
이 때 위 그림과 같이 (1,2)(2,3)(5,4)연결되었을 때, 이러한 '연결성'을 코드로 구현한 알고리즘이 바로 "UNION-FIND"다.
이 표처럼 2번째 인덱스 값엔 3, 3번째엔 1, 5번째엔 4가 들어간다.
보편적으로 부모를 합칠 때에는 더 작은 값 쪽으로 합친다.
이것이 바로 "UNION"(합침) 이다.
근데, 이때 한가지 의문이 생길 것 이다.
"어떻게 하면 1과2이 연결되었단 걸 알 수 있을까?"
1과 2의 부모는 각각 1과 3이므로 다르기 때문에 부모 노드로만 판단해선 제대로 알아보기 힘들다. 이러한 이유 때문에 재귀함수가 사용된다.
풀어서 설명해보자면
2의 부모를 찾으려면, 먼저 2가 가리키고있는 3으로 간다. 2에서는 1을 가리키고, 1에서는 1을 가리키니 최종적으로 2의 부모는 1이 된다.
위와 같은 과정을 재귀적으로 수행 했을때 가장 효과적이고 직관적이게 표현할 수 있다.
Reference
