[C++] 1717번 집합의 표현 - 자료 구조, 분리 집합

1. 문제

• 초기에 {0}, {1}, ..., {n}이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과 두 원소가 같은 집합에 있는지 확인하는 연산을 수행하려 한다.

<문제>

• - 1 -   \(n, m(1 \leq n \leq 1,000,000, 1 \leq m \leq 100,000)\)
  • m은 입력으로 주어지는 연산의 개수
• - m개의 줄 -   각각의 연산
  • 0 a b: 합집합
    • a에 있는 집합과 b가 있는 집합 합치기
  • 1 a b: 두 원소가 같은 집합에 포함되어 있는지 확인
  • \(0 \leq a, b \leq n\)

<출력>

• 1로 시작하는 입력에 대해 YES/NO로 결과를 출력

2. 재정의

• 집합 연산

3. 해결 방법

• 트리를 이용한 union-find 수행

4. 실수한 점, 개선할 점

• rank랑 union은 이미 표준 라이브러리에 있는 단어이므로 사용할 수 없어서 node_rank, Union을 대신해서 사용하였다.
• 노드 번호를 기준으로 트리를 연결하면 소요 시간이 줄어드는데 왜 그런지는 잘 모르겠다. 그냥 한 것 같고 우연인 것 같다. 그냥 랭크로 하는 게 더 효율 좋은 듯.

 

<코드>

#include <iostream>

using namespace std;

const int MAX_N = 1000001;

// <문제>
// 집합의 개수 n, 연산의 개수 m
int N, M;

// 부모 노드 root, 노드 차수 rank
int root[MAX_N], node_rank[MAX_N];

void input() {
    cin >> N >> M;
    for(int i=0; i<MAX_N; i++) {
        root[i] = i;
        node_rank[i] = 0;
    }
}

// 루트 노드 반환
int find(int x) {
    if(root[x] == x)
        return x;
    else
        // find 연산 최적화
        return root[x] = find(root[x]);
}

// 트리를 합치기
void Union(int x, int y) {
    x = find(x), y = find(y);
    
    // 두 값의 root가 같으면 합치지 않는다.
    if(x == y)
        return;
    
    // Union-by-rank 최적화
    // 항상 높이가 더 낮은 트리를 높이가 높은 트리 밑에 넣는다.
    if(node_rank[x] < node_rank[y])
        root[x] = y;
    else {
        root[y] = x;
        
        // 만약 트리의 높이가 같다면 합친 후 (x의 높이 + 1)
        if(node_rank[x] == node_rank[y])
            node_rank[x]++;
    }
}

void solve() {
    for(int i=0; i<M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        
        // 두 원소가 같은 집합에 포함되어 있는가?
        if(a) {
            // 루트 노드가 같으면 같은 집합에 포함되어있다.
            if(find(b) == find(c))
                cout << "YES" << '\n';
            else
                cout << "NO" << '\n';
        }
        // 두 트리를 합치기
        else
            Union(b, c);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    solve();
    
    return 0;
}

 

<Union-find 알고리즘>

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

 

<왠지 모르겠지만 노드 번호를 기준으로 한 코드>

https://hongku.tistory.com/158

알고리즘 :: Union Find(Disjoint-Set) 알고리즘, 합 집합 찾기 알고리즘 (C/C++ /JAVA 구현)

 

<문제 바로가기>

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.