#1을 return find(parent[x]);라고 쓸려 한 것 같습니다.
경로압축에 데해 알아보세요.
유니온파인드에 관해 질문있어요
1717번 - 집합의 표현
#1
int find(int x) {
if(x==parent[x]) return x;
return find(parent[x]);
}
#2
int find(int x) {
if(x==parent[x]) return x;
return parent[x] = find(parent[x]);
}
#2의 find 함수는 x가 속한 트리의 루트 노드 값을 루트 노드에서 현재 노드까지 재귀적으로 반환합니다. 이 때 parent[x] = find(parent[x]); 코드는 재귀적으로 반환하는 각 과정(경로)에 있는 모든 노드의 부모 노드를 루트 노드로 바꾸어 주는 것을 의미합니다.
#1의 find 함수는 매번 루트까지 재귀호출을 해서 루트 노드 값을 얻어오는 반면, #2의 find 함수는 한 번 호출하면, 그 경로에 있는 모든 노드의 부모 노드가 루트가 됩니다. 따라서 그 다음부터 경로상에 있던 노드에 한해서 find 함수를 호출한다면, 루트노드를 찾기 위한 재귀 호출이 발생하지 않습니다. 그 이유는 재귀 호출 과정에서 이미 부모 노드를 루트 노드로 갱신해놨기 때문입니다. 따라서 O(1) 시간에 자신이 속한 집합을 알아낼 수 있습니다. 이를 '경로 압축 최적화' 라고 합니다.
@minjoonist 아.. 정확한 답변을 드리고 싶어서 계속 수정하다 보니 저렇게 됐네요 죄송합니다..
틀린 부분이 없다니 정말 다행입니다..
두 분 다 감사합니다
댓글을 작성하려면 로그인해야 합니다.
vincentlim1 6년 전
#1
int find(int x) {
if(x==parent[x]) return x;
return parent[x] = find(parent[x]);
}
#2
int find(int x) {
if(x==parent[x]) return x;
return parent[x] = find(parent[x]);
}
이 두 코드에 따라 시간복잡도 차이가 나는데 둘의 차이점이 뭔지 잘 모르겠어서요
차이가 뭔가요?