Union-Find 알고리즘
- Disjoint-Set을 구현할 때 사용하는 알고리즘이다.
- 크루스칼 알고리즘에서 최소 신장 트리(MCT)를 찾는데 사용된다. 간선이 연결될 때, 사이클의 발생여부를 확인하기 위해 사용된다.
Disjoint-Set
서로소 집합 자료구조라 부른다.
- 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. A 집합과 B 집합이 있을 때, 각각의 집합의 요소들은 다른 집합에 존재하지 않는다. 즉, 서로 교집합이 없다.
구현
union 함수와 find 함수를 만들어서 알고리즘을 구현한다.
- union(parent, x, y)
- 두 노드의 부모노드를 같게 만들어주는 함수이다.
- 입력 인자로 각 노드에 대한 부모노드가 적힌 배열과 연결시킬 두 노드를 입력한다.
- 비교하는 두 노드의 부모노드가 같지 않다면 부모노드를 하나로 바꿔주는 로직이 존재한다.
- 비교하는 두 노드의 부모노드가 같다면 이미 연결된 것으로 판단 함수를 끝낸다.(부모노드가 같은데 연결을 시키게 되면 사이클이 발생한다.)
const union = (parent, x, y) => { const node1 = find(parent, x) const node2 = find(parent, y) if(node1 < node2) parent[node2] = node1 else parent[node1] = node2 }
- find(parent, x)
- 입력한 노드의 부모노드가 무엇인지 찾는 함수이다.
- 입력 인자로 각 노드에 대한 부모노드가 적힌 배열과 찾기위한 노드를 입력한다.
- parent 배열에서 해당 노드의 부모노드를 찾은 뒤 노드 값과 부모노드 값이 다르면 함수를 재귀호출하여 최상위 부모노드의 위치를 찾아간다.(노드 값과 부모노드값이 같은 경우가 최상위 부모노드이다.)
const getParent = (parent, x) => { if(parent[x] === x) return x else return getParent(parent, parent[x]) }
궁금증 해결
처음 Union-Find 알고리즘을 공부하며 각 함수에 대해서 공부를 할 때, 뭔가 이상하다는 생각이 들었다. union 함수를 통하면 서로소 집합이 하나로 합쳐지는건 알겠는데, 서로소의 부모노드에 대해서만 parent 배열의 값이 변경되다보니 그러면 집합의 나머지 애들은 어떻게 되는지 궁금증이 생겼었다.
예를 들어 {0, 1, 2} / {3, 4}가 있을 때, 현재 parent 배열의 값은 [0, 0, 0, 3, 3] 1번과 4번을 연결한다고하면 Union-Find 알고리즘을 적용하게되면 0번 노드와 3번 노드는 서로소 관계이므로 union 함수가 작동을 하게 될 것이다.
그 결과 {0, 1, 2, 3, 4} 집합이 만들어지지만 parent 배열의 값은 [0, 0, 0, 0, 3]으로 남아있게 된다. 여기에서 의문이 생겼었다. 하나의 집합으로 만들어졌지만, 4번 노드의 부모노드는 0이 되어야 정상이지만, parent 배열에서는 3번 노드를 가리키고 있기 때문이다.
처음에는 배열에서 나머지 노드들이 가리키는 부모노드의 값을 변경시켜야하나 싶었는데 코드를 추적해가며 생각해보니 그럴 필요가 없다는 것을 알게되었다.
예를 들어, 1번 노드와 4번 노드에 대한 Union-Find 알고리즘을 적용해보면 1번 노드의 부모노드는 0번 노드로 바로 나올 것이고, 4번 노드의 경우 다음의 과정이 실행된다.
- find(parent, 4)가 호출되면 4 !== 3 이므로 다시 find(parent, 3)이 호출된다.
- find(parent, 3)의 결과 3 !== 0 이므로 다시 find(parent, 0)이 호출된다.
- find(parent, 0)의 결과 0 === 0 이므로 0이 반환된다.
위의 결과로 나온 4번 노드의 부모노드는 parent에서는 3을 나타내지만 실질적으로 함수안에서 계산되면 0을 가리키는 것을 볼 수 있다.
