JAVA로 Union과 Find를 구현하기

소개글

JAVA로 Union과 Find를 구현하기에 대한 보고서 자료입니다.

목차

1. 프로그램 소스파일

2. sample input.txt

3. sample output.txt

본문내용

input.txt을 샘플 input.txt를 통해 설명하겠다
17
19
union 1 2
union 3 4
union 1 3
union 5 6
union 7 8
union 5 7
union 1 5
union 9 10
union 11 12
union 9 11
union 13 14
union 15 16
union 13 15
union 9 13
union 9 17
union 1 9
find 2
find 15
find 14

맨 처음 17은 node의 개수이다.
그러면 1-17까지의 숫자를 가진 노드가 생성된다.
그 다음 19는 operation의 개수이다. 이 operation은 union, find를 의미한다. 그 다음은 union과 find가 있는데, union의 경우 두 트리 중에서 한 값씩을 뽑아 두 값을 넣어주고 find는 그냥 한 값을 넣어준다.

output.txt

12 6 6 12 6 7

순서대로 Union(weight rule) path compaction
Union(weight rule) path splitting
Union(weight rule) path halving
Union(height rule) path compaction
Union(height rule) path splitting
Union(height rule) path halving
에 따른 노드의 포인터 변경 횟수를 의미한다.
즉 총 횟수를 의미한다.

지금의 경우에는 find의 개수가 적어 큰 차이가 없지만 find를 많이 첨부해주면 각 방식에 따른 순위를 매길 수가 있다.

키워드

java,   자바,   union,   find,   argc[],   weight rule,   height rule,   path compaction