[알고리즘] 자바로 Union Find 구현하기

유니온 파인드란?

• 그래프/트리의 대표적 알고리즘
• 서로소인 부분집합의 표현
• 여러 노드가 있을 때, 두 노드가 같은 그래프에 속해 있는지 알 수 있는 알고리즘
• 두가지 메소드로 구현 가능 : union(x, y), find(x)

유니온 파인드 알고리즘이란, 하위 노드의 부모 노드를 배열에 저장하는 방식으로, 여러 노드들이 어떤 집합에 속해 있는지를 알 수 있는 유용한 알고리즘이다.

 

유니온 파인드를 능숙하게 사용할 수 있게 되면, 백준 등 여러 코딩 문제들도 손쉽게 풀 수 있다.

 

 

코드 구현

find

find() 는 int 변수를 파라미터로 받는 재귀함수이다. 파라미터로 넘긴 노드의 젤 최상위 부모가 누구인지를 알려주는 함수이다.

public int find(int x) {
	if(parent[x] == x) return x;  //최상위 노드는 자기 자신을 부모로 갖는다.
    return find(parent[x]);       //최상위 노드가 아닐 경우, 해당 노드의 부모 노드로 find 호출
}

 

 

union

union() 은 합칠 두 개의 노드를 파라미터로 받아 두 개 노드가 속한 집합을 합치는 함수이다. Union Find 알고리즘의 경우 합치기를 원하는 집합의 최상위 노드의 부모를 다른 집합의 최상위 부모로 지정을 하면 결국은 하나의 집합이 되기 때문에 find를 이용하여 적은 cost로 손쉽게 합칠수 있다.

public boolean union(int x, int y) {
	// 입력받은 두개 노드의 최상위 노드를 찾는다.
    x = find(x);
    y = find(y);
    
    if(x == y) return false;  // 최상위 노드가 같은 경우, return false
    
    if(x <= y) parent[y] = x; // 집합 합침
    else parent[x] = y;
    return true;
}

 

 

그 외 선언

public class Main {
	static int[] parent;
    
    static boolean union(int x, int y) { ... };
    static int find(int x) { ... };
    
    public static void main(String[] args) {
    	parent = new int[10] // 사이즈 초기화
        
        for(int i = 0; i < 10; i++) {  //parent 배열 초기화
        	paren[i] = i;
        }
        
        /*
        .
        .
        .
        ToDo
        .
        .
        .
        */
  	}
}

 

 

아래 링크는 Union Find 알고리즘을 활용한 백준 사이트에 있는 문제를 해결한 코드입니다. 사용법을 구체적으로 알고싶다면 참고하기 바랍니다.

2023.09.20 - [코딩 문제 풀이/백준] - [백준] 자바 문제 풀이 10216 : 골드4

[백준] 자바 문제 풀이 10216 : 골드4