tpwls8122   3달 전

 이전 작업 0이 했던 정보를 가지고 작업 1일때 YES or NO로 출력합니다.

만약 작업 1 a b 일때 union(a,x) || union(b,x)를 한적이 없었다면 parent배열은 자기 자신을 가리킬것이고 (대표노드였다면 자기자신) ,

union을 했다면 자기가 속한 집합의 대표 노드를 가리킬것입니다. 결론적으로 이전에 연결정보가 있었다면 parent배열은 같은 노드를 가리킨다. 

그래서 작업 1을 할 때, parent 배열을 쓰면 O(1)로 바로 접근 가능한데, find()를 쓰면 재귀를 사용하지않나요?

물론 답이 출력시 find()를 활용해야 정답인데, parent배열로 출력 시 왜 오답이 뜰까요

제가 잘못 이해했기 때문에 틀렸을텐데, 이유좀 알려주세요..

djm03178   3달 전

union을 한다고 해서 기존의 두 집합 내의 모든 원소가 즉시 루트를 가리키게 되는 것이 아닙니다. find를 통해 루트까지 따라올라가본 뒤에야 그 경로 상의 모든 원소들의 parent가 비로소 새로운 루트가 되는 것이고, 이 과정을 거치지 않은 원소들은 기존의 parent(루트가 아닐 수 있는)를 그대로 가지고 있는 상태입니다.

tpwls8122   3달 전

와 맞네요..ㄷㄷ감사합니다

댓글을 작성하려면 로그인해야 합니다.