유니온 파인드

정의

• 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 (자신의 대표 노드를 찾아주는) find 연산으로 구성되어 있는 알고리즘

특징

• union 할 땐 항상 대표 노드끼리 연결함

• 연결된 걸 표현할 땐 배열에서 자식 노드를 인덱스로 한 값에 대표 노드를 저장

• find는 단순히 대표 노드만 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 향상시킴
• 경로 압축의 효과 : 여러 노드에서 거쳐야 하는 경로에서 그래프 변형해 더 짧은 경로로 갈 수 있도록 해 시간 복잡도 효과적으로 줄임
• 예시) find 연산 속도가 O(1)로 변경됨

과정

1. 대표 노드를 저장하는 배열에 인덱스를 그대로 값으로 넣어주어 초기화

2. 2개의 노드 선택해 각각의 대표 노드를 찾아(find해) union 연산 수행
• find
1. 대상 노드 배열에 index 값과 value 값이 동일한지 확인
2. 동일하지 않으면 value 값이 가리키는 index 위치로 이동
3. 이동 위치의 index 값과 value 값이 같을 때까지 1~2번을 반복 (재귀 함수로 구현)
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서, 거치는 모든 노드 값을 루트 노드값(=대표 노드 값)으로 변경

예시

• 초기화 → [1,2,3,4,5,6]

• union(1, 4) → find(1)=1, find(4)=4 → [1,2,3,1,5,6]

• union(5,6) → find(5)=5, find(6)=6 → [1,2,3,1,5,5]

• union(4,6) → find(4)=1_find(1)=1, find(6)=5_find(5)=5 → union(1,5) → [1,2,3,1,1,5]

• union(2,6) → find(2)=2, find(6)=5_find(5)=1_find(1)=1 → [1,2,3,1,1,1] → union(2,1) → [1,1,3,1,1,5]
• [1,2,3,1,1,1] → find(6)=5 에 대해 후엔 find(6)=1이 나오게 변경

코드

💡

전체 코드와 추천 문제는 아래에서 확인하실 수 있습니다.

GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다. - GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

https://github.com/ChooSeoyeon/algorithm/tree/main