1. 의미

"합집합 찾기"라는 의미를 가진 알고리즘.

“서로소 집합” 알고리즘

2. 왜 사용하는가?

아까 말했듯이, 원소간의 연결 여부등을 알기 위해서 사용함.

3. 어떻게 쓰는가?

유니온 파인드에서는 크게 3가지 기능이 있다.

1. Set (초기화)
2. Union (합치기)
3. Find (찾기)

각각에 대해서 알아보자!

1. Set(초기화)

배열을 초기화하는 부분이다.

그것 말고는 딱히 기능이 없다.

2. Union(합치기)

두 원소의 대표배열을 정하여서 저장하는 기능이다.

두 원소들의 부모 배열을 갖게한다.

3. Find(찾기)

원소들끼리 연결되어 있는 지 확인하는 기능이다.

원소의 대표원소를 반환해주는 기능이다.

Union Find 예제 및 정답코드

예제 문제

---

오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다. 현수는 각 학생들의 친구관계를 알고 싶다. 모든 학생은 1부터 N까지 번호가 부여되어 있고, 현수에게는 각각 두 명의 학생은 친구 관계 가 번호로 표현된 숫자쌍이 주어진다. 만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학 생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다. 그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다. 학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램 을 작성하세요. 두 학생이 친구이면 “YES"이고, 아니면 ”NO"를 출력한다.

▣ 입력설명 첫 번째 줄에 반 학생수인 자연수 N(1<=N<=1,000)과 숫자쌍의 개수인 M(1<=M<=3,000)이 주어지고, 다음 M개의 줄에 걸쳐 숫자쌍이 주어진다. 마지막 줄에는 두 학생이 친구인지 확인하는 숫자쌍이 주어진다.

▣ 출력설명 첫 번째 줄에 “YES"또는 "NO"를 출력한다.

---

입력

20 22
18 9
4 15
12 16
9 10
10 7
14 9
13 3
17 5
6 1
1 14
12 4
9 11
7 5
17 4
6 17
12 9
18 10
17 8
11 18
7 19
4 3
3 4
10 15

---

출력

YES

---

정답코드

void Set()
{
    int i;
 
    for (i = 1; i <= n; i++)
        parent[i] = i;
    // Setting Array
}

// Set Function

 
void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
 
    if (x != y) // 두 원소의 배열이 다르면(친구가 아니면)
        parent[x] = y; // 두 원소의 부모를 갖게함(친구가 되게함)
}

// Union Function

int Find(int v)
{
    if (parent[v] == v) // 부모가 같으면(친구면)
        return v; // 부모를 리턴(대표친구를 리턴)
    else
        return parent[v] = Find(parent[v]); // 해당 원소의 대표친구의 부모를 다시 확인하게함
}

// Find Function

int main(void)
{
 
    int m, i,a, b;
 
    scanf("%d %d", &n, &m);
 
    Set(); // 초기화
 
    for (i = 0; i < m; i++)
    {
        scanf("%d %d", &a, &b);
 
        Union(a, b); // A 원소와 B 원소를 Union(합치기)를 함.
    }
 
    scanf("%d %d", &a, &b);
    if (Find(a) == Find(b)) // A 원소와 B 원소의 부모가 같으면(친구이면)
        printf("YES\n");
    else
        printf("NO\n");
 
    return 0;
}

틀린 것이 보이시면 댓글 남겨주세요!!