인프런 커뮤니티 질문&답변

작성한 질문수

Do it! 알고리즘 코딩테스트 with JAVA

[유니온 파인드 실전 문제] 집합 표현하기 (백준 1717)

집합 표현하기(백준 1717) union 함수 질문

해결된 질문

작성

·

320

1

안녕하세요 강의 잘 보고 있습니다.
강의를 보다가 질문이 생겨 질문드립니다.

강의 영상에서 union 함수에서 a,b의 크기와 상관없이
a와 b가 다르다면 parent[b] = a; 라고하시는데
이렇게 해도 되는 이유가 어차피 나중에 find 함수의 재귀함수부분 return parent[a] = find(parent[a]); 에서 경로 압축이 되기 때문에 크기 상관없이 parent[b] = a; 선언 해주신 건가요?

java 코딩-테스트 알고리즘

답변 1

1

지식공유자

안녕하세요 반갑습니다.

일반적으로는

if(a<b) parent[b] = a;

else if(a>b) parent[a] = b;

이렇게 작은수를 항상 root노드로 선정하거나 문제에 따라 반대로 일관되게 구현 합니다.

다만 해당 문제에서는 특별히 이렇게 통일해야하는 제약조건이 보이지 않았고 말씀하신대로

경로압축을 하면 크게 성능에도 문제가 없다고 생각하여 크기에 상관없이 유니온을 하였습니다.

일반적으로는 대부분 작은 수가 root노드가 되도록 많이 하시더라구요.

(문제의 조건이 있으면 꼭 조건에 맞게 구현하셔야합니다.!!)

감사합니다. 즐거운 하루되세요 :)

질문자

친절한 답변 감사합니다. 좋은 밤 되세요 :)

작성한 질문수