Union-Find 개념 정리 (C)

BSSM 알고리즘 수업

피곤하다.

Union-Find가 뭐임

의미

그래프 알고리즘으로 Union(합집합) + Find(찾다), '합집합 찾기' 라는 의미를 가지고 있다.

연산

2가지 연산이 존재한다.

1. Find(x): 원소 x가 속한 부분집합을 찾는다. 보통 x가 속한 부분집합의 대표 원소를 되돌려준다.
2. Union(x, y): 원소 x가 속한 부분집합과 원소 y가 속한 부분집합의 합집합을 구한다.

• 각 부분집합은 트리로 나타낸다.

구현해보셈

#include <stdio.h>

#define MAX 1001  // 최대 원소 수 정의

int parent[MAX];  // 각 원소의 부모 노드를 저장하는 배열
int rank[MAX];    // 각 원소의 트리 높이를 저장하는 배열

// 1. 초기화 함수: 모든 원소가 자기 자신을 부모로 가지도록 설정 (자기 자신만을 포함하는 독립된 집합)
void set(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;  // 처음에 각 원소는 자기 자신을 부모로 가짐
        rank[i] = 0;    // 초기에는 트리의 높이(rank)는 0으로 설정
    }
}

// 2. find 함수: 원소 x가 속한 집합의 대표(최종 부모)를 찾음
// 경로 압축(Path Compression)을 사용하여 트리의 깊이를 줄여주는 역할을 함
int find(int x) {
    // x가 자신의 부모가 아니라면 (즉, 루트가 아니라면)
    if (parent[x] != x) {
        // 재귀적으로 부모를 찾으면서 경로 압축 (부모를 루트로 직접 연결)
        parent[x] = find(parent[x]);
    }
    // 최종 부모(루트)를 반환
    return parent[x];
}

// 3. union 함수: 두 원소 x와 y가 속한 집합을 합침
// 트리의 높이를 고려하여 더 작은 트리를 큰 트리에 붙이는 방식으로 최적화 (Rank-based Union)
void union_sets(int x, int y) {
    int rootX = find(x);  // x의 대표(루트)를 찾음
    int rootY = find(y);  // y의 대표(루트)를 찾음

    // 두 원소가 이미 같은 집합에 속해 있으면 합칠 필요가 없음
    if (rootX != rootY) {
        // 랭크(트리 높이)가 낮은 트리를 높은 트리에 붙임
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;  // rootY를 rootX 밑에 붙임
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;  // rootX를 rootY 밑에 붙임
        } else {
            // 랭크가 같으면 임의로 하나의 트리에 붙이고, 그 트리의 랭크를 1 증가시킴
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

int main() {
    int N, M;

    // 학생 수 N과 친구 관계 쌍의 개수 M을 입력받음
    scanf("%d %d", &N, &M);
    
    // 1. 모든 학생을 각각 독립된 집합으로 초기화
    set(N);

    // 2. M개의 친구 관계 입력받아 처리 (union 연산)
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        union_sets(a, b);  // 두 학생의 집합을 합침
    }

    // 3. 마지막에 두 학생이 친구인지 확인할 쌍 입력받음
    int student1, student2;
    scanf("%d %d", &student1, &student2);

    // 두 학생이 같은 집합에 속하는지 확인 (find 연산)
    if (find(student1) == find(student2)) {
        printf("YES\n");  // 같은 집합에 속하면 친구 관계
    } else {
        printf("NO\n");   // 다른 집합에 속하면 친구 관계가 아님
    
    }

    return 0;
}