(24.09.05) 코딩테스트 알고리즘 정리(유니온 파인드 알고리즘)

유니온 파인드 Union-Find 알고리즘은 코딩테스트 대비에서 거의 출제빈도가 적은 알고리즘으로 알고 있다.

 

하지만, 지금까지 가중치에 따른 Graphy 구조에서 어떤 "경로" 관해서 집중한 알고리즘이 있다면,

이번엔 같은 그룹 즉, 같은 루트에 해당하는 자료에서 특정 주어진 경로의 루트 값의 비교를 통해 같은 그룹인지 아닌지를 파악할 수 있도록 하는 알고리즘을 집중해서 찾아보고 학습을 해봤다.

 

생각보다 개인적올 이해하기가 살짝 어려워서 코드를 하나하나 쳐가면서 내가 스스로 낸 문제를 작성할 수 있었다.

---

유니온 파인드 Union-Find

• 서로소 집합(Disjoint Set)의 자료구조를 다루는데 사용되는 알고리즘
• 연결된 요소 즉, 그룹을 빠르게 찾아낼 수 있는 알고리즘
  • 그룹은 하나의 부모에 여러 요소가 포함되어있다는 뜻

유니온 파인드 Union-Find FLOW

1. 초기화

• 모든 요소는 자기 자신을 부모로 세팅, 독립적인 그룹으로 시작

2. Find

• 특정 요소가 속한 그룹 찾기 연산
  • 요소 끼리 같은 그룹 = 부모인지 확인을 위해
• 경로 압축 Path Compression
  • 시간 단축의 효율성을 활용
  • 요소의 부모를 로트로 연결하는 방식, 같은 그룹 요소 확인시 빠르게 찾을 수 있도록함

3. Union

• 서로 다른 두 요소를 하나의 그룹으로 합치는 연산
• 두개의 그룹으로 합치면서 트리 구조를 형성하도록 함
• 랭크 기반 합치기 Union by Rank
  • 트리 구조 Depth의 최소화 방식
  • 두 그룹을 합쳐야할 경우 더 작은 트리를 큰 크기의 트리 밑으로 붙여나가는 방식

같은 그룹인지 판별 유니온 파인드 활용 알고리즘

• 임의의로 스스로 15개의 요소의 관계를 설정하고, 요소 간 같은 그룹인지 확인하는 알고리즘작성

package Algorithm;

public class UnionFind {

  private static int[] parent; // 루트 역할을 할 것
  private static int[] rank; // 초기에 아직 안정해 졌을 때, 랭크 이므로 0

  public static void main(String[] args) {

    // 1~15 번 요소들 예제 세팅
    parent = new int[16]; // 0은 요소에 없기 때문에
    rank = new int[16];
    for (int i = 0; i < parent.length; i++) {
      parent[i] = i; // 초기 본인이 스스로 루트
      rank[i] =0; // 그만큼 0으로 랭크 전부 맞춤
    }

    // 임의의 요소와 관계 세팅
    union(1, 14);
    union(14, 11);
    union(6, 4);
    union(6, 12);
    union(12, 9);
    union(12, 2);
    union(4, 7);
    union(5, 10);
    union(8, 5);
    union(5, 3);
    union(8, 15);
    union(13, 3);

    int x = 9;
    int y = 7;

    int parentX = find(x);
    int parentY = find(y);

    if (parentX == parentY) {
      System.out.println(x + "와 "+ y + "는 같은 그룹입니다.");
    } else {
      System.out.println("같은 그룹이 아닙니다.");
    }
  }

  // Path Compression을 활용한 요소 그룹 찾기 연산 = root값 찾기
  public static int find(int x) {

    if (parent[x] != x) {
      parent[x] = find(parent[x]);
    }
    return parent[x];
  }

  // rank에 따른 Union 설정
  public static void union(int x, int y) {
    int rootX = parent[x];
    int rootY = parent[y];

    // 같은 부모로 묶기 시작
    if (rootX != rootY) {
      // 랭크를 비교해서 낮으면 밑으로 들어가게함
      if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
      } else if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY;
      } else {
        // 두 부모의 랭크가 같기 때문에 첫번째 값을 임의로 위로 설정시킴 + 부모 설정
        parent[rootY] = rootX;
        rank[rootX]++;
      }

    }
  }

}

 

---

예를 들어, 어떤 사람들이 모여있는데 어떤 조건에 의해서 각 사람들이 값을 가지게 되었을 때, 같은 값을 가진 사람들 또는 어떠한 조건에 의해 같은 유형으로 묶인 사람들을 Rank를 통해서 트리구조로 바꾸고 이를 통해 같은 그룹인지 판별하는데에도 빠르고 유용하게 사용을 할 것.

 

거기에다가 이미 Map에 저장이 되어있기 때문에, 비교를 할 때 매번 모든 자료를 순회를 하면서 진행할 필요가 없기 때문에 유용하게 사용할 알고리즘으로 생각된다.