quf9484   1년 전

안녕하세요,

항상 친절하게 답변해주시는 고수님들 :)

오늘도 질문이 있습니다. 아래는 union-find 제 코드입니다.

union 함수에서 부모 노드를 할당해줄때, 항상 최상위 부모 노드(find 값)을 할당 해주어야 하는 이유가 있나요?

첫 번째 union 함수 처럼 할당을 하여도, find 함수는 재귀적으로 호출하기 때문에 최상위 부모를 찾아서 비교 할 수 있는 것 아닌가요?

그래서 두 번째 union 함수는 성능 향상을 위한 목적이지 첫 번째 함수도 정답이라고 생각하는데 틀렸다고 나옵니다.

감사합니다!

yijw0930   1년 전

parent[a]=b에서 b는 최상위 부모 노드일 필요가 없지만 a는 최상위 부모 노드여야만 합니다.

위 식의 의도는 a와 연결된 모든 노드 c에 대하여 find(c)=find(b)가 되는 것인데, 만일 a가 최상위 노드가 아니라면 a의 최상위 노드에 find 연산을 한 값이 여전히 그 자신이 되기 때문입니다.

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