(JAVA) 백준 1717번 : 집합의 표현 --- [Disjoint-Set]

www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

안녕하세요.

 

Disjoint-Set 중 Union-Find 알고리즘을 사용한 문제입니다.

 

이 문제는 기본적인 문제입니다. (저는 한 번 틀렸죠.. 실수해서)

 

 

크게 어려울 건 없습니다.

 

입력받을 때

 

  -  맨 앞 숫자가 0이면 : union(a, b)

  -  맨 앞 숫자가 1이면 : isSameParent(a, b) -> 부모가 같으면 YES /// 다르면 NO 

 

 

이 때, 메모리 효율성과 시간 단축을 위해

 

a와 b가 같은 경우에 대한 예외 처리까지 진행합니다.

 

a == b 이면 어차피 부모 값 또한 같겠죠?

a == b 이면 Union 의미없죠?

 

함수 호출을 줄이려는 것입니다!

 

 

 

이상입니다.

감사합니다!

 

 

소스코드

---