r을 구하는 과정에서 딱히 잘못된 건 없어 보입니다.
사실 원래 질문과 추가 질문은 하나의 원인에서 나온 것 같습니다.
s[prt[b]] 때문인데요.
이를 s[find(b)] 로 바꾸면, 이후에 r을 추가해도 정답이 나오고 혹은 s[find(a)]로 바꿔도 정답이 나올 것 같습니다.
prt[b] 는 b의 부모 노드일 뿐이고, b의 루트를 제대로 호출하는 건 find(b)이기 때문입니다.
위의 소스에서 s[prt[b]] 로 했을 때 정답이 나온 이유는, merge(a,b) 를 할 때 y=find(y) 에서 prt[b] 가 find(y) ( = 루트= Line32이후의 y) 의 값을 저장했기 때문입니다.
Line 32 : prt[x] = y; 에서 루트를 y로 선택했기 때문에 printf 에서도 여전히 prt[b]가 최종 루트(y)를 저장하고 있습니다.
반대로 s[prt[a]] 가 오답이 나온 이유는, merge(a,b) 에서 x=find(x)를 하더라도, prt[a] 가 find(x)를 저장하지, 최종 루트값은 저장하지 않기 때문입니다.
Line 32 : prt[x] = y; 에서 최종 루트가 y 로 바뀌어 버렸기 때문에, prt[a] 는 최종 루트(y)를 가리키지 않게 됩니다. 여전히 x를 저장하고 있죠.
(x=find(x) 이후엔 a!=x일 수 있습니다)
원래 질문에서 r 을 추가했을 때, 오답이 나오는 이유도 비슷한 것 같습니다.
swap(x,y); 가 이루어 졌을 경우 최종 루트가 바뀌어, printf 에서 prt[b] 가 최종 루트값을 저장하지 않고 있기 때문이죠.
위에서 prt[a] 가 최종 루트를 가리키지 않는 이유와 비슷합니다.
마지막으로 prt[string형]=string 이냐, prt[string형]=int 이냐는... 정답이 없는 거 같네요.
개인적으로 그냥 취향차이라고 생각합니다.
제 취향에는 오히려 prt[string형]=string 가 더 맞습니다... 꼭 int 로 저장해야 문제의 시간제한 & 메모리제한을 통과할 수 있는 경우만 아니라면요.
저같은 경우엔 prt[string형] = int은 'string에 번호 붙여놓았음.' 이라는 생각의 과정이 하나 더 추가되는 느낌이 들어서 그렇게 좋아하진 않습니다...
his130 6년 전
union-find 를 이용해서 문제를 풀었습니다.
처음에 트리의 갯수와 높이를 모두 알기 위해, s 와 r 로 구현하였습니다.
그런데 이게 계속 실패가 떠서 , 높이를 구하는 r을 제거하고 s만으로 아래 코드와 같이
r은 모두 주석처리를 하니 정답이 되었습니다.
r을 구하는 과정에서 어떤 오류가 발생하는 것인가요?
r을 구하는 과정이 잘못된 것인지, r을 구할때는 s를 구할 수 없는 것인지..
알려주실 수 있나요?
<<추가질문>>
그리고 제가 마지막에 정답을 출력할 때, s[prt[b]] 가 아닌 s[prt[a]] 를 출력해도 오답이 생기더라구요.
어차피 그 전에 merge 로 a,b를 묶으니 정답에 상관이 없어야 하는 것이 아닌가요?
그리고 제가 저런식으로 prt[string형]=string 형으로 문제를 풀었는데, 저러면 메모리 문제나 시간 문제가 발생할 수도 있을까요?
다른 분들 코드를 참고하니 모두 prt[string]=int 형으로 바꿔서 , 즉 노드에 번호를 매겨서 문제를 푸시더라구요.