Union-Find(유니온 파인드)에 대해 알아보고 구현하기

Union-Find(유니온 파인드)에 대해 알아보고 구현하기

반응형

Union-Find?

유니온 파인드. 그대로 해석하면 union은 조합, find는 찾다로 해석이 가능하다. 실제로 이 알고리즘은 두 연산 find와 union를 사용한다. 여러 개의 노드가 있다고 가정했을 때 2개의 노드를 union을 통해 합치는 것도 가능하고, find를 통해 해당 노드의 부모노드를 찾는 것 또한 가능하다.

전체적인 구현 방법

노드들의 부모를 나타낼 배열을 선언해줘야한다. 예를 들어 트리를 다룬다고 했을 때 직접적으로 간선을 옮겨주는 식으로 할 수 없는가? 라는 생각을 가질 수 있으나, 가능은 하나 노드들의 부모가 하나로 통일됬는 지 검사하는 등의 연산이 필요할 경우, 시간복잡도가 난해해지므로 O(n)으로 끝낼 수 있게 노드들의 부모를 나타낼 배열을 선언해줘야한다.

부모노드가 없을 경우 자기 자신을 가르키도록 해야한다.

노드 [0] [1] [2] [3] 부모 노드 0 1 2 3

(0번 노드의 부모는 0번, 1번 노드의 부모는 1번인 상태... 즉 부모노드가 없이 자기자신을 가르키고 있다.)

그리고 Find 함수를 만들어줘야한다.

Find함수는 내가 원하는 노드의 부모노드를 찾는 함수이다. 정확히는 원하는 노드의 루트노드를 찾는다. 즉 위에서 만든 노드들의 부모를 나타내는 배열인 parents 배열에서 부모노드를 찾으면 된다.

int find(int target){ if(target == parents[target]) return target; else return find(parents[target]); }

이런식으로 target과 parents[target]이 같으면 target을 리턴하고, 틀리면 parents[target]을 find함수의 인수로 넣어 값을 가져온다.

Union 함수는 매개변수를 2개를 받는다. 즉 내가 원하는 2개의 노드의 부모를 찾은 뒤 같다면 넘기고, 2개의 노드의 부모가 서로 다르다면 번호가 빠른 노드의 자식으로 나머지 노드를 달아준다.

int Union(int a, int b){ a = find(a); b = find(b); if(a!=b){ if(a

Union-find의 장점

만약 여러 개의 노드 무리들이 있다고 가정했을 때, 2개의 노드를 선택했을 때 그 노드들이 연결이 되어있는지 찾기가 용이하다.

위에 그림처럼 노드들이 있다고 가정했을 때, find를 통해 3번 노드와 5번 노드가 같은 트리인지 쉽게 찾을 수 있고, union을 통해 3번과 5번을 연결하는 것도 가능하다.

노드 [0] [1] [2] [3] [4] [5] [6] 부모노드 0 0 0 2 4 4 4

또한 O(n)이라는 효율적인 시간복잡도를 가지고 있다.

2번 노드와 3번 노드가 연결되어있는 지 확인하는 코드

#include using namespace std; int parents[4] = {0,1,2,3}; int find(int target){ if(target == parents[target]) return target; else return find(parents[target]); } int Union(int a, int b){ a = find(a); b = find(b); if(a!=b){ if(a

연습하기 좋은 문제

https://www.acmicpc.net/problem/1976

유니온 파인드 알고리즘이 개념이 좀 직관적이기 때문에, 나름 이해하는 것 자체는 쉬운데 문제의 랭크들이 좀 높게 되어있다.

끝맺는 말

알고리즘이 직관적이라 재밌고, 효율적인 알고리즘이니 확실히 익혀두도록 하자.

반응형

from http://everydaywoogi.tistory.com/133 by ccl(A) rewrite - 2021-10-14 11:00:41