arr[x] = 를 추가함으로써 경로압축이 이루어집니다.
Parent[0] = 1, Parent[1] = 2 ... Parent[5] = 5 인 상황을 가정하고 Find(0)을 여러번 호출하려고 합시다
arr[x] = 이 없으면, 한번 Find(0) 호출시에 5번의 재귀호출이 일어나고 최종적으로 최상위노드인 5를 리턴할겁니다. 그리고 다시 한번 Find(0)을 호출시에도 똑같이 5번의 재귀호출이 일어나겠죠.
허나 arr[x] = 이 있으면, 처음 한번 Find(0) 호출시에는 위와같이 5번의 호출이 일어나긴 합니다만 5번의 재귀호출이 끝나면
Parent[0] = 5, Parent[1] =5 ... Parent[5] = 5 으로 할당되어서 다음 Find(n) (n은 0~5까지의 수) 호출시엔 5번의 재귀호출까진 필요없이 단번에 최상위노드인 5를 리턴합니다.
재귀다 보니깐 적어가면서 추적하는 것이 어려워서 저 같은 경우는 그냥 최상위노드까지의 경로를 압축하는 용도구나 까지만 이해하고 있습니다.
위의 Parent배열에 할당이 잘못 적혀 있을 수도 있는데 저런 식으로 압축이 된다는 것은 확실합니다.
tprjs456 2년 전
코드 16번째 줄 return arr[x]= union_find(arr[x]);
이 부분에서 arr[x]= 이라는 부분이 왜 들어가야하는지 union_find(arr[x]); 만들어가면 왜 시간 초과가 뜨는지
36번째 줄인 arr[union_find(vec[i])] = union_find(union_find(vec[i]) - 1); 와 겹치는 내용이 아닌지
궁금합니다. 부탁드리겠습니다!!