[JS] 간단한 유니온-파인드 알고리즘 구현하기

📚 문제

책에 있는데 간단하게 유니온-파인드 알고리즘을 구현해보는 것!

📣 풀이

• 시도한 풀이

  function find(parents, x) {
      if (parents[x] === x) {
          return x;
      }
  
      parents[x] = find(parents, parents[x]);
      return parents[x];
  }
  
  function union(parents, x, y) {
      const root1 = find(parents, x);
      const root2 = find(parents, y);
  
      parents[root2] = root1;
  }
  
  function solution(k, operations) {
      const parents = Array.from({ length: k }, (_, k) => i);
      let n = k;
  
      for (const op of operations) {
          if (op[0] === 'u') {
              union(parents, op[1], op[2]);
          }
          else if (op[0] === 'f') {
              find(parents, op[1]);
          }
  
          n = new Set(Array.from({ length: k }, (_, i) => find(parents, i))).size;
      }
  
      return n;
  }

💫코드 리뷰 & 반성

[어려웠던 점]
유니온-파인드 알고리즘에 대해 처음 공부해서 그런지 코드를 떠올리는 게 쉽지 않았다.
그래도 공부해보니 걱정한 거보다는 어렵지 않은 거 같다!

[새롭게 알게된 점]
파인드는 재귀 사용해주고 유니온은 각 집합의 루트 노트 찾아서 하나의 루트 노드로 합쳐주기.

Set은 중복이 허용되지 않는 자료구조이기에 find를 사용해서 노드마다(인덱스를 활용)
루트 노드 찾아준 다음 개수는 size로 구해주기.

참고

코딩 테스트 합격자 되기 자바스크립트 - 이선협, 박경록 저