Union Find알고리즘

- 합집합을 찾을 때 주로 사용

- 서로소 집합 알고리즘이라고도 함

- 여러 노드 중에서 그룹화를 지을 때 사용하는 알고리즘

- 크루스칼 알고리즘 구현 시 싸이클이 발생하지 않도록 판별할 때 사용하는 등 다양한 알고리즘 문제 적용시 사용이 됨

- 무방향 그래프에서 적용

 

*문제 상황

 

- 노드의 연결 정보는 현재 위와 같다는 문제가 주워져 있다

- (1,2,3)이 한 그룹, (4,5)이 한 그룹이다.

 

*구현 방법

1, 일차원 배열 (parent)으로 해당 노드의 부모의 값을 적용하도록 한다.

-  배열안의 있는 값은 노드의 부모의 값을 저장하도록 한다. (이때, 부모는 배열안의 수가 자기 자신인 노드를 지칭한다.)

- 초기 설정은 해당 노드의 부모가 자기 자신으로 초기 설정을 해 준다.

 

초기 parent배열

 

 

2, 부모를 찾는 메소드를 구현하여 준다(findParent)

- 해당 인덱스와 배열의 수가 동일하면 그 노드는 부모노드이다.

- 만약 같지 않다면 재귀적으로 배열 안에 있는 수의 노드의 부모를 찾아 나서도록 구현하여 준다.

public int findParent(int search){
        if(parent[search] == search) return search;

        return parent[search] = findParent(parent[search]);
    }

 

2, 간선의 정보를 하나하나 받아와서 부모를 갱신하는 메소드를 구현(unionParent메소드 정의)

- 두 노드의 부모들을 찾은 다음 한 노드의 부모에 다른 부모를 연결하여 최종 부모가 한 노드가 되도록 구현

 public void unionParent(int a, int b){
        int aParent = findParent(a);
        int bParent = findParent(b);

        parent[aParent] = bParent;
    }

 

3,노드의 연결 정보를 받아와 parent배열을 갱신하여 준다.

전체코드

package com.company;

import java.util.ArrayList;
import java.util.List;


public class UnionFind {

    static class Edge{
        int node1;
        int node2;

        public Edge(int node1, int node2){
            this.node1 = node1;
            this.node2 = node2;
        }
    }

    static int[] parent = new int[6];

    public static int findParent(int search){
        if(parent[search] == search) return search;

        return parent[search] = findParent(parent[search]);
    }

    public static void unionParent(int a, int b){
        int aParent = findParent(a);
        int bParent = findParent(b);

        parent[aParent] = bParent;
    }

    public static void main(String[] args) {
        //간선의 정보를 저장
        List<Edge> map =new ArrayList<>();
        map.add(new Edge(1,2));
        map.add(new Edge(1,3));
        map.add(new Edge(4,5));

        for(int i = 1 ; i < 6; i++){
            parent[i] = i;
        }

        for(Edge e: map){
            unionParent(e.node1, e.node2);
        }

        for(int i = 1; i < 6; i++){
            System.out.println(i +  ": " + parent[i]);
        }
    }
}

실행결과

- 첫번째 그룹의 부모노드는 3으로, 두번째 그룹의 부모노드는 5로 묶인 것을 확인 할 수 있다.

 

해당 글은 블로그를 참고하여 정리하였습니다.

m.blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)