Union find

Union Find는 내장 라이브러리가 없어서 필요할 때 많이 만들어서 사용한다.

사용 방법에 따라서 input과 output이 달라지는 문제때문에 그런거 같아 보이긴 한데, 짐작이다.

그래서 조금하게 클래스를 하나 만들어 봤다.

Union find는 크게 2개의 기능으로 이루어 진다.

• Find : 특정 키를 갖고 있는 값의 Root를 찾는다.
• Union : 2개의 키를 하나의 Root로 합친다.

여기에 하나 더해서 내부에서 사용할 Set을 만드는 기능도 필요한데, 그냥 find 넣으면 set을 만든다 생각하고 만들지 않았다.

class UnionFind{
    constructor(){
        this.map = new Map();
    }

    find(key){
        key = JSON.stringify(key);
        if(!this.map.has(key)) {
            this.map.set(key, key);
        } else {
            let curKey = this.map.get(key);

            if (this.compare == null && curKey != key) {
                this.map.set(key, this.find(curKey));
            } else if (this.compare != null) {
                if(!this.compare(JSON.parse(curKey), JSON.parse(key))){
                    this.map.set(key, JSON.stringify(this.find(JSON.parse(curKey))));
                }
            }
        }
        return JSON.parse(this.map.get(key));
    }

    union(left, right){
        let leftKey = JSON.stringify(this.find(left));
        let rightKey = JSON.stringify(this.find(right));

        this.map.set(rightKey, leftKey);
    }

    compare = null;
}

JSON을 사용한건 객체 키 때문이다.

Map 내부적으로 키를 Compare 할때 "===" 로 Type Compare 까지 하게 되는데, Array같은 객체들은 내부 값이 비록 같을 지라도 서로 다른 객체로 인식 되기 때문에 문제가 발생 한다.

[1,2]와 그 다음에 조회를 들어오는 [1,2]는 다른 객체가 된다. 그래서 key는 Primitive Type을 쓰는게 좋은데, 그냥 범용적으로 사용 가능할 까 싶어서 JSON으로 객체 String 변환을 했다.

 

사용 방법은 아래와 같다.

특이한건 compare 인데 객체 키값의 경우 compare방식을 사용자가 선택 할 수 있게 만들었는데, 생각해 보니까 어짜피 stringify로 string으로 만든 상태 인데, 이게 무슨 의미가 있나 싶다.

let unionFind = new UnionFind();

unionFind.find('A');
unionFind.find('B');
unionFind.find('C');
unionFind.find('D');
unionFind.find('E');

unionFind.union('A','B');
unionFind.union('C','D');

console.log(unionFind.find('B'));
console.log(unionFind.find('D'));

console.log(unionFind.union('B', 'D'));
console.log(unionFind.find('B'));
console.log(unionFind.find('D'));
console.log(unionFind.find('E'));
console.log(unionFind.union('E', 'A'));
console.log(unionFind.find('D'));

let unionFind2 = new UnionFind();

unionFind2.compare = (a, b) => a[0] === b[0] && a[1] === b[1];
unionFind2.find([0,0]);
unionFind2.find([0,1]);
unionFind2.find([1,0]);
unionFind2.find([1,1]);

console.log(unionFind2.find([0,0]));


unionFind2.union([0,0],[0,1]);
unionFind2.union([1,0],[1,1]);

console.log(unionFind2.find([0,1]));
console.log(unionFind2.find([1,1]));


unionFind2.union([0,1],[1,1]);
console.log(unionFind2.find([1,1]));

 그래도 만든거니 그냥 붙여 둔다.

상기 Class는 Set의 전체 순환을 외부에서 처리하는 방식이라 시간 복잡도를 말하긴 뭐하지만,

외부에서 특정 Set을 부르는 것 까지 생각했을 때

• N개의 Set으로 이루어져 있고

• union find 작동이 M회 실행 된다

고 했을 때,

시간 복잡도는 O(N+MlogN) 이라고 하는데 잘 모르겠다.

www.slideshare.net/WeiLi73/time-complexity-of-union-find-55858534

Time complexity of union find

나중에 상기 내용을 잘 읽어보고 이해하면 추가 하겠다.