11724번 - 연결 요소의 개수
아래는 되는 소스입니다. 그런데
void union_find(int a, int b) { int root_a = find(a); int root_b = find(b); // 주석에 적은 대로 작성을 하면 틀리게 됩니다. if (root_a < root_b) { //parents[b] = root_a; parents[root_b] = root_a; } else { //parents[a] = root_b; parents[root_a] = root_b; }}\
union_find 부분에서
parents[root_b]를 parents[b] 로 바꾸면 틀리게 됩니다.
저는 find 함수에서 갱신이 다 될 것이라고 생각했는데 아니었습니다.
혹시 안 되는 직관적인 이유를 알려주실 수 있으신가요? 감사합니다.
A : 1
B : 2 <- 3
인 상황에서
merge(1,3)을 하면 잘못된 코드로는
A : 1 <- 3
B : 2
가 됩니다.
A : 1 <- 2<- 3
이 되어야 맞습니다.
감사합니다. find() 한 것과 상관없이 나의 최종 부모가 아니라 그냥 받은 값들을 잇고 끝나는군요.
댓글을 작성하려면 로그인해야 합니다.
cjswodmlskfk 4년 전
아래는 되는 소스입니다. 그런데
void union_find(int a, int b) {
int root_a = find(a);
int root_b = find(b);
// 주석에 적은 대로 작성을 하면 틀리게 됩니다.
if (root_a < root_b) {
//parents[b] = root_a;
parents[root_b] = root_a;
} else {
//parents[a] = root_b;
parents[root_a] = root_b;
}
}\
union_find 부분에서
parents[root_b]를 parents[b] 로 바꾸면 틀리게 됩니다.
저는 find 함수에서 갱신이 다 될 것이라고 생각했는데 아니었습니다.
혹시 안 되는 직관적인 이유를 알려주실 수 있으신가요? 감사합니다.