rhjung2001   1년 전

아래 코드의 union_parents 함수에서 case1의 코드를 사용하면 정답 처리가 되는데, case2의 코드에서는 시간초과가 나옵니다.

왜 그런걸까요?

dh0450   1년 전

크루스칼 알고리즘에는 최적화 기법이 두개가 있습니다. 

자세한건 https://www.secmem.org/blog/20... 

짧게 설명하면 Path 줄이는 것과 균형트리로 만드는 것이 있는데 위 코드에는 Path 줄이는 최적화를 잘못구현되어 있습니다.

return a = find_parents(parents[a]);

=> return parents[a] = find_parents(parents[a]);

이러면 통과될것으로 보입니다.

rhjung2001   1년 전

바로 이해가 됐습니다. 감사합니다 :)

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