유니온 파인드

유니온 파인드

현대 오토에버 코딩테스트 문제로 출제되었다
전에 풀어보았던 플로이드-워셜 알고리즘 형태의 문제인 줄 알고
2차원 배열을 생성하여 풀었더니, 대략 10^4, 10000 정도 까지는 괜찮았는데, 256MB의 메모리 제한 때문인가
그 이상으로 생성할 경우 메모리초과가 발생했다

플로이드-워셜은 그래프에서 노드들이 연결되어있는지 확인하는 알고리즘이고, 이와 다른 유니온 파인드가 존재함을 알았다(사실 전에 풀었었는데 기억조차 못하고 있었다)
또한 플로이드 워셜은 O(N^3)의 시간복잡도를 가진다

문제 자체에서 팀을 2개로 분할이 가능한가를 묻는 문제였기 때문에 굳이 전체를 연결할 필요 없이
같은 집합인지 아닌지만 확인하면 되는 문제...
이로인해 유니온 파인드 알고리즘에 대해 다시 찾아보게 되었다

유니온 파인드 연산이란?

여러 노드가 존재할 때 서로 연결되어있는지 확인

union: 특정 2개의 노드를 연결하여 1개의 집합으로 묶는 연산

find: 두 노드가 같은 집합에 속해있는지 확인하는 find 연산

유니온 파인드의 원리

1. 1차원 배열 안에 값을 자신의 인덱스로 초기화 하기
   Why? 처음 연결이 없는 상태에서는 자신이 대표 노드가 되기 때문이다

// 배열의 이름은 parent로 보통 설정하나 보다
// 참고로 만일 노드가 1~10까지면, +1 된 크기의 배열을
// 선언하는 것이 편하다
// Why? 노드가 대부분 0이 아닌 1부터 시작하기 때문에

int[] parent = new int[11]; // 배열 선언

// 자기 인덱스 값을 자신의 값에 설정
for(int i = 1; i < 11; i++) {
	parent[i] = i;
}

2. 노드를 연결하는 union 연산을 실행한다
   [union(1,4)]
   union 연산을 실행하는 경우, 1과 4를 연결한다고 가정해본다
   이 경우 parent[4]의 대표 노드를 1로 수정해준다
   [union(5,6)]
   5와 6을 연결하는 경우도 가정하면
   parent[6]의 대표노드도 5로 수정된다
   그런데 4와 6처럼 대표노드가 다른 녀석들을 연결하는 경우가 중요하다
   [union(4,6)]
   여기서 find 연산을 사용해야 한다
   4와 6 둘 다 대표 노드가 아니기 때문에
   4의 대표 노드 1과, 6의 대표 노드 5를 연결해서 값을 변경한다

public static void union(int a, int b) {
	// 만일 a의 대표 노드와, b의 대표 노드가 다르다면
	if(find(a) != find(b) {
    	// 해당 배열의 b값의 대표노드를 찾아 이동하여
        // 이것을 a의 대표 노드로 변경해준다
    	parent[find(b)] = find(a);
    } else {
    	// 만일 find(a)와 find(b)가 같다면?
        // 사이클이 생긴 것이다
    }
}

3. find 연산은 자신이 속한 대표 노드 값을 찾는다
   추가로 찾는 연산과 더불어 시간 복잡도를 향상시켜준다

// 1. parent 배열의 index와 value가 같은지 확인
// 2. 다르면 value 값의 인덱스로 이동
// 3. 이동 위치 index 값과 value 값이 같을 때 까지 반복 - 재귀로 구현
// 4. 대표 노드로 도달하면 return 하면서 해당 index의 value들을 모두
//    마지막 노드값으로 변경
public static int find(int a) {
	// index a의 값과 그 value 값이 같다면
	if(a == parent[a]) {
    	return a; // 그대로 a 값을 반환해준다(자신이 대표노드)
    } else {
    	// 그렇지 않다면, a의 값은 대표 노드를 찾아
        // 그 값으로 계속 변경하고 값 리턴
    	return parent[a] = find(parent[a]);
    }
}

활용

그래프 문제에서 사이클이 존재하는지 확인
=> 사이클 존재는 union 단계에서 확인 가능하다

시간 복잡도는 O(N) 또는 O(logN)
실제 시간 복잡도는 O(a(N)),
a(x)는 에커만 함수 - 재귀 성능 체크
(if x = 2^65536) a(x) = 5 (상수처리?)

참고

Do it 알고리즘 코딩테스트 자바편