vjerksen   2년 전

두 원 사이의 관계 중 " (원의 중심 사이의 거리) <= (두 원의 반지름의 합) " 일 때, Union & Find로 그룹지었습니다.

어디에서 논리적 오류가 있는 지, 문법 오류가 있는 지 가르침 부탁드립니다..


h0ngjun7   2년 전

아래와 같이 수정하시면 맞을 수 있습니다.

vjerksen   2년 전

to. appa

정말 감사합니다! 근데 질문이 하나 있는데요.

find에서 자식이 부모의 값을 저장해놔도, 부모가 새로운 부모를 가지면 기존의 부모 값을 가지던 자식들은 저장 값이 바뀌지 않는 것으로 보이는데요.

for (int i = 1; i <= N; i++) parent[i] = _find(i);

위와 같은 for문을 모든 union & find 문제에 써야하나요? 다른 간단한 방법은 존재하지 않나요?

haja   2년 전

parent[i] == find(i) 일때만 카운트 하는 방법이 있습니다.

vjerksen   2년 전

to. haja
조금만 더 설명 부탁드려도 될까요?

haja   2년 전

각각의 집합에 대해서 parent[i] == find(i) 즉, 부모가 자기 자신인 노드는 하나 밖에 없다는 말입니다. 그래서 이러한 노드의 개수만 세면 집합의 수를 구할 수 있습니다.

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