[최소신장트리] Union Find

Union-Find 알고리즘은 최소신장트리 알고리즘에 많이 쓰이지만 사실은 서로소 집합을 찾는 알고리즘이다. 

 

서로소 집합은 서로 중복 포함된 원소가 없는 집합들, 즉 교집합이 없는 집합이다.

따라서 집합에 속한 하나의 특정 멤버인 대표자를 이용해 각 집합들을 구분한다. 

 

서로소 집합을 표현하는 방법에는 대표적으로 연결 리스트와 트리가 있다.

연결 리스트

- 같은 집합의 원소들은 하나의 연결리스트로 관리하고, 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.

- 즉, 연결리스트의 헤드가 대표자가 되는 것이다. 

- 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다. 

 

트리

- 트리도 연결리스트와 비슷하다. 자식 노드가 부모 노드를 가리키며, 루트 노드가 대표자가 된다.

 

이런 서로소 집합들을 서로 연결 시켜주기 위해 union-find 알고리즘을 사용한다.

union find 알고리즘은 make(), findSet(), union(x,y) 함수로 이루어져 있다.

 

make 함수는 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산이다. 

parent는 부모의 인덱스를 저장해주는 배열인데, 처음에 서로소 집합을 만들어 주기 위해 본인을 부모로 가지게 설정했다.

static void make() {
		//자신의 인덱스랑 같은 번호를 넣어줌.
		for(int i=0; i<N; i++) {
			parents[i] = i; 
		}
	}

두 번째로는 findSet 함수이다. 

compression 전 함수를 쓰면 계속해서 타고타고 올라가야하는데, compression을 해서 아예 root 번호를 저장하게 만들어 두면 연산 횟수를 줄일 수 있다. 이 전에는 parents속 값이 부모 인덱스를 가리켰다면, 이 함수 이후에는 parents가 root를 가리키게 된다. 

static int findSet(int a) {
		//만약 내가 대표자면 나 리턴
		if(parents[a] == a) return a;
		
		//path compression 전.
		//return findSet(parents[a]);
		
		//path compression 후.
		//이 코드 쓰는게 더 좋음.
		return parents[a] = findSet(parents[a]);
	}

 

세 번째로는 union 함수이다.

이 함수는 인자로 받아주는 a와 b값을 findSet에 넣어서 root가 같은지 다른지 확인해준다.

root가 같다면 이미 같은 집합 안에 속해있는 것이므로 false를, 다르다면 다른 집합에 속해있는 것이므로 b의 루트를 a의 루트에 연결해주고 true 를 리턴해준다.

 

static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if(aRoot == bRoot) //둘이 같다면 이미 같은 집합에 속해있는 것
			return false;
		//다르다면 A밑에 B붙임.
		parents[bRoot] = aRoot;
		return true;
	}

이 코드를 응용하면 최소신장트리인 크루스칼 알고리즘을 만들 수 있다.

크루스칼 알고리즘은 다음 글에서 다뤄보려고 한다:)