문제해결기법[Alliance]- (Union-Find 자료구조)

문제해결기법 수업 동맹(Alliance)문제이다.

주어진 문제를 풀기위해 진짜 .... 20시간정도를 투자하였는데 ..... 결국 못풀고 어쩌다보니 Union-Find 자료구조를 알게 되었다.

자세한 참고는 이곳을 통하여 배우게 되엇다. (http://blog.secmem.org/521)

일단 나의 방식으로 설명하자면 트리의 구조이다.

다른 트리와 다른점이 있다면 트리간의 연결성, 즉 같은 그룹안에 속해있는지 아닌지를 판별하는데 아주 좋은 자료구조라고 볼 수 있다.

Union_Find 자료구조를 구성하기 위한 기본 3가지 함수이다.

init 함수는 맨처음 자기자신을 head로 하는 n개의 트리를 각각 만드는 것이다.

find함수는 각각의 그룹이 어떤 그룹에 속해 있는지 head를 반환해주는 함수이다.

unite함수는 2 개의 입력이 주어지면 그 2개의 입력을 같은 그룹으로 묶어 주는 함수이다.

신긔방기 ........ 

위에 사이트 참고 하고 나중에 필요할때 다시 생각해보도록 하자 !!