🔗 Union-Find 알고리즘 구현 예제 (C 언어)

이번 포스팅에서는 Union-Find 알고리즘을 C 언어로 구현한 예시를 소개하겠습니다. 이 알고리즘은 그래프 문제에서 서로소 집합을 관리할 때 유용하게 사용되며, 주로 사이클 검출이나 최소 신장 트리를 찾을 때 많이 활용됩니다.

아래 예제에서는 두 가지 주요 연산인 Find와 Union을 통해 집합을 관리하고, 마지막에 두 노드가 같은 집합에 속해 있는지를 판별합니다.

📂 코드 설명

#include<stdio.h>

int n, parent[1001];  // 노드 개수와 부모 배열 선언

// 🕵️‍♂️ Find 함수: 해당 노드가 속한 집합의 대표(루트) 노드를 찾는 함수입니다.
int Find(int v)
{
    if (parent[v] == v)
        return v;  // 루트 노드이면 자기 자신을 반환합니다.
    else
        return parent[v] = Find(parent[v]);  // 경로 압축으로 부모를 루트로 갱신하며 반환합니다.
}

// 🔗 Union 함수: 두 집합을 합치는 함수입니다.
void Union(int x, int y)
{
    x = Find(x);  // x의 루트를 찾습니다.
    y = Find(y);  // y의 루트를 찾습니다.

    if (x != y)
        parent[x] = y;  // 두 루트가 다르면 y를 x의 부모로 설정합니다.
}

// 🛠️ 초기화 함수: 모든 노드의 부모를 자기 자신으로 설정합니다.
void Set()
{
    int i;
    for (i = 1; i <= n; i++)
        parent[i] = i;  // 처음에는 각 노드가 자기 자신을 부모로 가집니다.
}

int main(void)
{
    int m, i, a, b;

    scanf("%d %d", &n, &m);  // 노드 개수와 연산 횟수를 입력받습니다.
    Set();  // 초기화합니다.

    // 🔄 m번의 Union 연산을 수행합니다.
    for (i = 0; i < m; i++)
    {
        scanf("%d %d", &a, &b);
        Union(a, b);  // a와 b를 같은 집합으로 합칩니다.
    }

    // ❓ a와 b가 같은 집합에 속하는지 확인합니다.
    scanf("%d %d", &a, &b);
    if (Find(a) == Find(b))
        printf("YES\n");  // 같은 집합에 속하면 YES를 출력합니다.
    else
        printf("NO\n");  // 그렇지 않으면 NO를 출력합니다.

    return 0;
}

---

📚 주요 함수 설명

1️⃣ Find(int v)

• 이 함수는 재귀를 사용하여 해당 노드 v가 속한 집합의 루트 노드를 찾습니다.
• 경로 압축 기법을 사용하여 탐색 효율성을 높입니다. 즉, 탐색하면서 만나는 모든 노드가 루트 노드를 직접 가리키도록 갱신합니다. 🚀

2️⃣ Union(int x, int y)

• 두 노드 x와 y를 같은 집합으로 합병하는 역할을 합니다.
• 두 노드의 루트가 다르면 x의 루트를 y의 루트로 갱신하여 합칩니다. 🔗

3️⃣ Set()

• 모든 노드의 부모를 자기 자신으로 초기화하는 함수입니다. 초기 상태에서는 각 노드가 자기 자신이 루트입니다. 🌱

🧪 실행 예시

입력:
5 4
1 4
2 4
3 4
4 5
1 5

출력:
YES

설명

1. 6개의 노드가 있고 4번의 Union 연산을 수행합니다.
2. 마지막으로 1과 5가 같은 집합에 속해 있는지 확인할 때, YES가 출력됩니다. 🎉

---

📝 결론

Union-Find 알고리즘은 서로소 집합을 효율적으로 관리할 수 있는 대표적인 알고리즘입니다. Find와 Union 연산을 통해 집합을 병합하고, 경로 압축 기법으로 성능을 최적화할 수 있습니다. 💡

그래프 탐색이나 사이클 검출 문제에서 자주 사용되니 꼭 익혀두시기 바랍니다. 😎

---

❓ 추가 질문

궁금한 점이 있거나 코드에 대한 문의사항이 있으시면 언제든지 댓글로 남겨주세요! 🤗