유니온 파인드란?
원소들의 집합을 표현하는 자료구조 중 하나.
서로 다른 두 개의 집합을 병합하는 Union 연산과 해당 집합에 원소가 속해있는지 검색하는 Find 연산을 합쳐 Union-Find라 부릅니다.
유니온 파인드는 최소 신장 트리(MST)의 크루스칼 알고리즘에서 주로 사용되는 자료구조이기도 합니다.
Union
각 노드가 속한 집합을 1개로 합치는 연산.
노드 a,b가 a ∈ A, b ∈ B 에 속한다면, Union(a,b)는 A ∪ B를 말합니다.
즉, a와 b의 대표노드를 하나로 병합하는 과정입니다.
Find
특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산.
노드 a가 a ∈ A에 속한다면, Find(a)는 A집합의 대표 노드를 반환합니다.
구현 과정
Parent
자기 자신을 대표 노드로 삼는 새로운 배열을 생성합니다.
해당 배열은, Union과 Find 연산에 사용될 합집합 배열입니다.
Union
Union 연산을 할 두 개의 노드를 입력받아, 각 노드의 대표 노드를 하나로 묶습니다.
예를 들어, Union(1,3)과 Union(2,4)를 연산한다고 했을 때. 이를 그림으로 표현하면 다음과 같습니다.
1과 3은 대표노드는 1로 묶였으며.
2와 4는 대표노드는 2로 묵인 것을 확인할 수 있습니다.
이를 통해 네 개의 숫자가 두 개의 집합으로 병합되어, 관리가 가능합니다.
만약 여기서 2번 집합의 대표노드인 2번 원소가 1번 집합에 묶이게 된다면, 위와 같이 바뀌게 됩니다.
2번 원소의 대표노드가 자기 자신이 아닌, 1번으로 바뀌게 되고.
맴버 원소인 4번은 여전히 2번을 가리킵니다. 하지만, 4번 원소가 대표노드를 Find할 경우, 이전과는 다르게 1번을 가리키게 될 것입니다.
Before : Find(4) => 4 → 2 / return == 2
After : Find(4) => 4 → 2 → 1 / return == 1
Find
파인드는 자신이 속한 집합의 대표노드를 찾는 연산입니다.
대상 노드 배열의 인덱스 값과 value가 일치하는 지 체크하고, 동일하지 않는다면 value가 가리키는 index로 이동하여 대표 노드를 확인합니다.
만약 현재 parent 배열의 상태가 {1,1,1,2,5}일 때. Find(4)를 연산하면,
그 처리과정은 다음과 같습니다.
인덱스가 4이지만, value가 2이기 때문에 일치하지 않습니다.
index-4 != vlaue-2
따라서 value2를 index로 삼아서 대표 노드를 다시 확인합니다.
(여기서 경로 압축이 가능합니다.)
index-2 != value-1
여전히 value와 index가 일치하지 않기 때문에, value 1을 index로 넘겨서 더 깊이 들어갑니다.
index-1 == value-1
value와 index가 일치하므로, 4번 원소의 대표노드는 1번이 됩니다.
재귀함수를 빠져나오면서 거치는 모든 노드값의 대표 노드 값으로 변경할 경우에,
경로 압축이 가능하게 됩니다.
경로 압축을 이용한다면 해당 원소가 속한 집합의 모든 원소가 직접적으로 최상위 루트를 가리키게 되어 경로의 길이가 줄어드는 효과가 있습니다.
경로 압축이 적용되어있다면 원소 4를 Find할 때.
대표노드값을 1로 바꾸어서, parent 배열에 저장되는 값은 최종적으로 1, 1, 1, 1, 5가 됩니다.
코드 구현
유니온 파인드를 이용하여 친구 네트워크의 크기를 구하는 문제입니다.
문제에서 요구하는 것은 input으로 받은 a가 속한 집합의 크기를 출력하는 것입니다.
사람의 이름은 int가 아닌 string으로 저장해야하기 때문에,
parent배열은 vector나 배열이 아닌, Map을 이용해서 저장할 것입니다.
또한, 집합의 크기를 저장하기 위해서 Map을 추가로 선언하여, 값을 관리합니다.
main함수에서는 parent와 visited 맵에 킷값을 추가하면서, 초기 값을 설정합니다.
이후, Union함수를 통해서, a와 b를 같은 집합으로 묶어줍니다.
최종적으로 visited 맵에서 키 a의 대표노드에 해당하는 value를 출력해줍니다.
이를 통해서, 집합의 크기를 출력할 수 있습니다.
유니온 함수는 입력받은 두 원소를 하나의 집합으로 묶어주는 역할을 합니다.
만약 a와 b의 대표 노드가 같지 않다면, parent[b]를 a로 바꾸어서 a의 집합 맴버로 병합합니다.
그리고, b를 집합의 원소로 받아들였으니, b가 보유하고 있던 집합의 크기를 이양하여 a의 집합 크기를 갱신해줍니다.
파인드 함수는 해당 원소가 속한 집합의 대표노드를 찾아가는 함수입니다.
경로압축 기법을 적용하여, 재귀함수 간에 호출되는 모든 값을 대표노드로 바꾸는 로직도 추가되어 있습니다.
