Algorithm

유니온 파인드 (Union Find) - Java

2023. 2. 28. 12:05
728x90
반응형

유니온 파인드란?

유니온 파인드는 여러 노드가 있을 때 특정 2개의 노드를 연속적으로 연결하여 하나의 집합으로 묶는 union 연산과 특정 노드의 루트 노드를 찾는 find 연산으로 이루어진 알고리즘입니다.

유니온 파인드는 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘으로, 집합 관계를 판별할때 주로 사용합니다. 그리디 알고리즘 중 하나인 크루스칼 알고리즘에서도 사이클을 판별하기 위해 사용합니다.

 


 

예시

  • 7개의 섬이 있다고 가정해보겠습니다. 각 섬은 다리로 연결되어 있어, 연결된 섬끼리는 자유롭게 이동할 수 있습니다.
  • 즉, 섬 4 - 3 - 5 는 각 섬끼리 다리로 연결되어 있기 때문에 같은 집합이라고 보는 것이죠. 반대로 섬 1에서 4로는 갈 수 없기 때문에 다른 집합으로 생각합니다.
  • 이러한 집합의 개념을 union find 에서는 배열에 값을 저장하여 나타냅니다.

 

 

  • union find 알고리즘으로 집합을 표현한 모습입니다.
  • int 형 배열 각 인덱스에 값을 갱신해주면서 같은 값이면 같은 집합으로 분류합니다.
    • 집합 - 1 {1, 2}  /  집합 - 3 {3, 4, 5}  /  집합 - 6 {6, 7}
  • unionfind에서는 노드 N의 집합관계를 구할 때 int[] 배열에 접근하여 값을 얻는것이 아닌, find 알고리즘을 사용합니다.

 

 

find 연산

private int find(int a) {
    if (union[a] == a) return a;
    
    // 재귀함수 호출
    // 거쳐간 모든 노드의 집합을 갱신함 -> 시간 복잡도 ↓
    return union[a] = find(union[a]);
}
  •  find 연산은 노드가 어느 집합에 소속되어 있는지 판별할 수 있는 값을 반환합니다.
  • unionFind[n] != n 이라면 재귀함수를 통해 unionFind 배열의 인덱스와 저장된 값이 같아질 때까지 반복하고 값을 반환합니다.
  • 재귀를 통해 집합을 탐색하는 과정에서 거쳐간 모든 노드의 값을 갱신해주면서 시간 복잡도를 줄입니다.
    • ex) 위 예시에서 find(5) = 3 

 

union 연산

Union 연산은 두 노드 A, B를 하나의 집합으로 묶는 연산입니다. find 연산을 사용하여 두 집합관계를 묶습니다.

앞서, 예시로 보여드린 집합관계를 union 연산을 통해 나타내어보겠습니다.

 

int[] union 배열 초기화

int[] union = new int[n + 1];

// union 배열 초기화
for (int i = 1; i < union.length; i++) {
    union[i] = i;
}

  • 모든 노드에 대해 각 인덱스의 값을 저장하는 int 형 배열을 생성하고 초기화합니다.

 

 

Union 연산 수행

- 예시 코드 - 

// 섬 연결 정보
int[][] islands = {{1, 2}, {4, 5}, {3, 4}, {6, 7}};

for (int i = 0; i < islands.length; i++) {
    int A = islands[i][0];
    int B = islands[i][1];

    if (find(A) != find(B)) {
       union(A, B);
    }
}

private void union(int a, int b) {
    int A = find(a);
    int B = find(b);

    if (A != B) union[B] = A;
}

private int find(int a) {
    if (union[a] == a) return a;
    // 거쳐간 모든 노드의 집합을 갱신함 -> 시간 복잡도 ↓
    return union[a] = find(union[a]);
}

 

 

  • 먼저 1과 2를 묶어보겠습니다. 우선 두 노드에 대해 find 연산을 수행합니다.
    • find 연산은 인덱스와 값이 동일하면 반환해주기 때문에 find(1) = 1, find(2) = 2 입니다.
  • 두 값이 다르다면 다른 집합으로 판단하여 union 배열의 값을 갱신합니다.
    • union[2] = 1;

 

 

  • 이제 4와 5를 묶어주겠습니다. 앞선 과정과 동일하게 find(4) 의 값과 find(5)의 값을 비교하여 다르다면 union 배열의 값을 갱신해줍니다.
    • 집합 - 1 {1, 2}  /  집합 - 4 {4, 5}

 

 

  • 3와 4를 묶어주겠습니다. 앞선 과정과 동일하게 find(3) 의 값과 find(4)의 값을 비교하여 다르다면 union 배열의 값을 갱신해줍니다.
  • 이제 3,4,5 는 같은 집합이 되었습니다. 여기서 union 배열에 들어있는 값은 각각 (3, 3 ,4)로 다른 것을 확인할 수 있습니다. 하지만 find 연산을 이용하면 결국 노드 3, 4, 5는 같은 값을 반환하게 됩니다.

 

 

  • find 연산은 union 배열의 index와 저장된 값이 같지 않다면 재귀 호출을 통해 값을 탐색합니다.
  • 이 과정을 통해 union[5]에는 4가 저장되어있지만, find(5) 는 3을 반환하게 됩니다.
    • 이 때, 거쳐간 노드의 union 배열 값을 갱신해주면 다음과 같이 같은 값을 저장하게 됩니다. 

 

 

 

 

결과 

  • 위와 같은 과정을 모두 거치면 다음과 같이 나타낼 수 있습니다.
  • find 연산을 통해 union 배열을 탐색하여 같은 집합인지 알 수 있습니다.
  • 또한, 같은 집합 내에서 두 노드를 연결하면 사이클이 생기기 때문에 사이클 생성 유무를 판별하기위해 사용되기도 합니다.

 

 

728x90
반응형
저작자표시 (새창열림)
  1. 유니온 파인드란?
  2.  
  3. 예시
  4. find 연산
  5. union 연산
  6. int[] union 배열 초기화
  7. Union 연산 수행
  8. 결과 
'Algorithm' 카테고리의 다른 글
  • [SQL] 프로그래머스 - 입양 시각 구하기(2)
  • [프로그래머스] LEVEL3. 이중우선순위큐 - java
  • [프로그래머스] LEVEL2. 더 맵게 - java
  • [프로그래머스] LEVEL2. 가장 큰 수 - java
KAispread
KAispread
개발에 관련된 학습 내용들을 기록하는 공간입니다.
반응형
KAispread
기억의 정류장
KAispread
전체
오늘
어제
  • All (120)
    • Language (27)
      • Java (14)
      • JavaScript (4)
      • Principle (2)
      • Summary (7)
    • Web (10)
      • Template (4)
      • Base (6)
    • Spring (7)
    • Test (7)
    • JPA (23)
      • Spring Data JPA (9)
      • Base (14)
    • AWS (10)
    • DevOps (8)
      • Monitoring (2)
    • Database (10)
    • Algorithm (9)
    • Project (1)
    • Git (1)
    • 생각 정리 (4)
    • IDE (3)
      • eclipse (1)
      • Intellij (2)

블로그 메뉴

  • 🌈 GIthub
  • 🌎 LinkedIn
  • 📝 Notion
  • 🧑🏻‍💻 Resume

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.
글쓰기 관리자
KAispread
유니온 파인드 (Union Find) - Java
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.