qazxcv6090   4년 전

유니온 파인드를 통해 무게를 같이 갱신해주었습니다.

시간을 줄이기 위해서 자주 사용되는 fnd함수를 수정해야할것같은데

아무리 생각해도 더 빠르게 만들수 없어서 질문드립니다.

djm03178   4년 전

union find에서 사용되는 최적화 기법이 여러 가지 있는데 대표적인 것 첫 번째는 경로압축, 두 번째는 rank 최소화입니다. 이 코드는 둘 중 어느 것도 수행하고 있지 않습니다. 27, 31번째 줄의 조건은 단순히 부모의 번호를 비교할 뿐이므로 최악의 경우 시간 복잡도에서 아무런 득을 볼 수 없습니다.

qazxcv6090   4년 전

감사합니다. 최적화 기법을 따로 공부해서 도전해보겠습니다.

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