집합(Set)

• 수학에서의 집합: 어떠한 명확한 조건을 만족시키는 서로 다른 대상들의 모임

• 컴퓨터과학에서의 집합: 순서와 중복이 없는 원소들을 갖는 자료구조

• 코테에서 필요한 집합은 상호배타적 집합(Disjoint Set)

  ⇒ 서로 겹치지 않는 원소들로 이루어진 여러 집합

  ⇒ 교집합이 없는 집합관계
  

• 상호배타적 집합을 통해 서로 다른 집합들을 효율적으로 관리할 수 있게 해줌

🔠 상호배타적 집합 개념

고려할 점

• 특정 집합 원소들이 하나의 집합의 원소라는 것을 알 수 있어야 함
• 각 집합이 빠르게 다른 집합이라는 것을 알 수 있어야 함
• 특정 원소가 어느 집합에 속하는지 알 수 있었어야 함
• 2개의 집합을 하나로 합칠 수 있어야 함

집합을 배열로 나타내기

• 각 원소는 자신의 부모 노드를 가리키며, 루트는 자신을 가리킴

  ⇒ 배열의 인덱스는 원솔르 나타내고, 해당 인덱스의 값은 부모 노드를 가리킴

  ⇒ 루트 노드의 경우 자기 자신을 가리키도록 하며, 존재하지 않는 노드는 -1로 표시
  

• find(9)로 노드 9의 루트노드를 찾는 과정

  1. 현재 노드와 부모 노드가 같을 때까지 탐색 과정을 반복
  2. 현재 노드 9의 부모노드는 3, 같지 않으므로 현재 노드를 부모노드인 3으로 변경
  3. 현재 노드 3의 부모노드는 7, 같지 않으므로 현재 노드를 부모노드인 7로 변경
  4. 현재 노드 7의 부모노드는 2, 같지 않으므로 현재 노드를 부모노드인 2로 변경
  5. 현재 노드 2의 부모노드는 2, 같으므로 현재 노드 2는 루트노드(루트노드를 리턴)

⏱️ 시간복잡도

• 초기화: O(1)
• 찾기(find): 평균 O(log N), 최악 O(n)
• 합치기(union): find 연산에 의존

⌨️ 구현하기

경로 압축과 랭크 합치기를 통한 최적화 기법 사용하여 구현

class DisjointSet {
    constructor(size) {
        // 각 요소의 부모를 자기 자신으로 초기화
        this.parent = new Array(size).fill().map((_, i) => i);
        // 각 요소의 랭크(트리의 높이)를 0으로 초기화
        this.rank = new Array(size).fill(0);
        this.size = size;
    }

    find(x) {
        // 경로 압축: x의 루트를 찾으면서 경로상의 모든 노드를 루트에 직접 연결
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y) {
        let rootX = this.find(x);
        let rootY = this.find(y);

        // 이미 같은 집합에 속해 있다면 합치지 않음
        if (rootX === rootY) {
            return false;
        }

        // 랭크에 의한 합치기: 항상 랭크가 낮은 트리를 랭크가 높은 트리 밑에 붙임
        if (this.rank[rootX] < this.rank[rootY]) {
            [rootX, rootY] = [rootY, rootX]; // rootX가 항상 랭크가 높거나 같게 만듦
        }
        this.parent[rootY] = rootX;
        
        // 두 루트의 랭크가 같았다면, 합친 후 랭크를 1 증가
        if (this.rank[rootX] === this.rank[rootY]) {
            this.rank[rootX]++;
        }

        return true;
    }

    // 두 요소가 같은 집합에 속해 있는지 확인
    connected(x, y) {
        return this.find(x) === this.find(y);
    }
}

// 사용 예시
const ds = new DisjointSet(5);
console.log(ds.connected(0, 2)); // false - 초기에는 연결되어 있지 않음
ds.union(0, 2);
console.log(ds.connected(0, 2)); // true - 0과 2를 연결했으므로 true
ds.union(1, 3);
ds.union(2, 4);
console.log(ds.connected(0, 4)); // true - 0-2-4가 연결되어 있으므로 true
console.log(ds.connected(1, 4)); // false - 1-3과 0-2-4는 별개의 집합

📍 참고

• 코딩테스트 합격자 되기 JS 편
• https://jh2021.tistory.com/35