크루스칼 알고리즘에는 최적화 기법이 두개가 있습니다.
자세한건 https://www.secmem.org/blog/20...
짧게 설명하면 Path 줄이는 것과 균형트리로 만드는 것이 있는데 위 코드에는 Path 줄이는 최적화를 잘못구현되어 있습니다.
return a = find_parents(parents[a]);
=> return parents[a] = find_parents(parents[a]);
이러면 통과될것으로 보입니다.
1647번 - 도시 분할 계획
크루스칼 알고리즘에는 최적화 기법이 두개가 있습니다.
자세한건 https://www.secmem.org/blog/20...
짧게 설명하면 Path 줄이는 것과 균형트리로 만드는 것이 있는데 위 코드에는 Path 줄이는 최적화를 잘못구현되어 있습니다.
return a = find_parents(parents[a]);
=> return parents[a] = find_parents(parents[a]);
이러면 통과될것으로 보입니다.
바로 이해가 됐습니다. 감사합니다 :)
댓글을 작성하려면 로그인해야 합니다.
rhjung2001 1년 전
아래 코드의 union_parents 함수에서 case1의 코드를 사용하면 정답 처리가 되는데, case2의 코드에서는 시간초과가 나옵니다.
왜 그런걸까요?