Union-Find 알고리즘이란?

서로소 집합(Disjoint-Set) 알고리즘이라고도 불리는 알고리즘으로 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다.

❓ Disjoint-Set(서로소 집합) 이란 무엇일까요?
👉 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조입니다. 즉, 공통 원소가 없는 부분 집합들로 나눠진 원소들에 대한 자료구조입니다.

Union-Find 알고리즘의 과정

Union find 알고리즘은 초기화(makeSet) - 합치기(union) - 찾기(find) 연산 과정을 거칩니다.

• 초기화(makeSet)
  union과 find 연산을 하기 전, 각 노드를 하나의 집합으로 초기화하는 과정
  ex) 0부터 5까지 노드가 있을 때 {0}, {1}, {2}, {3}, {4}, {5} 처럼 하나의 유일한 노드를 가지는 집합으로 만듭니다.

• 합치기(union)
  두 집합을 합치는 과정
  ex) 위의 예시에서 0과 1번 노드를 합친다면 {0,1}, {2}, {3}, {4}, {5} 처럼 집합이 합해져 하나의 집합이 됩니다.

• 찾기(find)
  주어진 노드가 속한 집합의 대표 노드를 반환

❓ 집합을 어떠한 자료구조로 구현하는 것이 좋을까?
👉 트리 구조가 가장 효율적인 자료구조로서 사용됩니다. 왜냐하면 트리 구조는 루트 노드가 존재하므로 대표 원소로 설정하기 용이합니다.

예시

1부터 6까지 노드가 있을 때 4개의 union 연산 union(1,4), union(2,3), union(2,4), union(5,6) 이 주어진 상태를 예시로 보자.

초기 상태

union 후 상태

1. 부모 테이블 초기화
   노드의 개수 크기의 부모 테이블을 초기화 한다. 초기값은 자기 자신을 부모로 가지도록 설정한다.

노드번호	1	2	3	4	5	6
부모	1	2	3	4	5	6

2. union 연산

• union(1,4) : 현재 루트 노드는 각각 1과 4이므로 더 큰 번호인 루트 노드 4의 부모를 1로 설정

노드번호	1	2	3	4	5	6
부모	1	2	3	1	5	6

• union(2,3) : 현재 루트 노드는 각각 2와 3이므로 더 큰 번호인 루트 노드 3의 부모를 2로 설정

노드번호	1	2	3	4	5	6
부모	1	2	2	1	5	6

• union(1,2) : 현재 루트 노드는 각각 1와 2이므로 더 큰 번호인 루트 노드 2의 부모를 1로 설정

노드번호	1	2	3	4	5	6
부모	1	1	2	1	5	6

• union(5,6) : 현재 루트 노드는 각각 5와 6이므로 더 큰 번호인 루트 노드 6의 부모를 5로 설정

노드번호	1	2	3	4	5	6
부모	1	1	2	1	5	5

union을 마친 상황

❓ 1과 3은 부모노드가 다른데 같은 집합인지 어떻게 확인할 수 있을까요?
👉 재귀함수를 사용해서 알 수 있습니다. 3의 부모를 찾기 위해서는 먼저 3이 가리키고 있는 2를 찾습니다. 그리고 2의 부모를 확인합니다. 그러면 2의 부모가 1을 가리키고 있으므로 그제서야 결과적으로 3은 1과 같은 집합이라는 것을 알 수 있습니다.

Union-Find 예제

📌 문제
4개의 인수가 매개변수로 들어온다. 첫번째 매개변수로는 노드의 수, 두번째 매개변수로는 연결상태를 나타내는 nums 배열, 3번째 매개변수와 4번째 매개변수로는 두 개의 노드번호가 들어온다. 두 개의 노드가 같은 집합에 속해있으면 YES를 출력하고 다른 집합에 속해있으면 NO를 출력한다.

📌 풀이

function solution(n, nums, s1, s2) {
  let answer = "YES";
  let parent_node = Array.from({ length: n + 1 }, (v, i) => i);
  function Find(v) {
    if (v === parent_node[v]) return v;
    else return (parent_node[v] = Find(parent_node[v]));
  }
  function Union(a, b) {
    let fa = Find(a);
    let fb = Find(b);
    if (fa !== fb) parent_node[fa] = fb;
  }
  for (let [a, b] of nums) {
    Union(a, b);
  }
  if (Find(s1) !== Find(s2)) return "NO";
  return answer;
}

• 부모 노드를 자기 자신으로 초기화

let parent_node = Array.from({ length: n + 1 }, (v, i) => i);

• 두개의 노드번호를 입력받아서 Union하는 함수

function Union(a, b) {
  let fa = Find(a);
  let fb = Find(b);
  if (fa !== fb) parent_node[fa] = fb;
}

• 연결 상태인 nums배열을 이용하여 union

for (let [a, b] of nums) {
    Union(a, b);
}

• 재귀를 이용하여 부모노드를 찾는 Find 함수

  function Find(v) {
    if (v === parent_node[v]) return v;
    else return (parent_node[v] = Find(parent_node[v]));
  }

• 두 개의 노드가 같은 집합인지 아닌지 확인

  if (Find(s1) !== Find(s2)) return "NO";