UnionFind 디자인 개선

[byeongkeunahn]

현재는 크기 n의 UnionFind 객체를 생성하려면 다음과 같이 두 줄이 필요합니다.

let mut uf = UnionFind::new();
uf.resize(n);

하지만 크기를 미리 알고 있는 경우가 많으므로 다음과 같이 할 수 있으면 좋을 것 같습니다.

let mut uf = UnionFind::new(n);

UnionFind::new의 시그니처를 수정하는 방법이 있고, 새로운 메서드를 추가하는 방법이 있습니다. 둘 중 어떤 게 좋을까요? 아니면 다른 방법이 있을까요?

그리고, UnionFind에서 현재 connected component 개수를 자동으로 추적해주면 편리할 것 같습니다.

[kiwiyou]

UnionFind::new의 시그니처를 수정하는 방법이 있고, 새로운 메서드를 추가하는 방법이 있습니다. 둘 중 어떤 게 좋을까요? 아니면 다른 방법이 있을까요?

UnionFind::new에 크기를 나타내는 인자를 추가하더라도 의미상 문제가 되지 않을 것 같고, 동시에 기능적으로 기존 new를 포용하므로 시그니처를 수정하는 편이 좋다고 생각합니다.

그리고, UnionFind에서 현재 connected component 개수를 자동으로 추적해주면 편리할 것 같습니다.

큰 오버헤드가 없어서 찬성합니다.

[byeongkeunahn]

아 그리고 UnionFind::find라는 메서드가 있을 거라고 생각했는데 UnionFind::root로 있어서 조금 당황했어요. 이름을 바꾸거나 alias를 추가하는 건 혹시 어떨까요?

[kiwiyou]

자료구조의 이름을 따라 find를 쓰는 것도 좋아 보입니다.

[byeongkeunahn]

현재 구현상 UnionFind::resize는 크기를 줄일 수 있는 걸까요? 없는 것 같긴 한데... 줄일 수 없으면 명시하려고 해요. Connected components 개수 추적하려면 개수가 줄어드는 건 이상하기도 해서요.

[kiwiyou]

현재 구현은 잘 줄어듭니다. 다만 연결 요소의 개수를 세게 되면 문제가 생기긴 하겠네요. 크기가 단조증가하도록 하면 좋겠습니다. UF가 애초에 뭔가 삭제하도록 만들어진 물건이 아니기도 하고요.