[알고리즘] Union-Find 알고리즘을 알아보자 with(상화 T)

윤도훈·2024년 9월 25일

Union Find 알고리즘

Union-Find 알고리즘이 뭐야?

: 유니온 파인드 알고리즘은 대표적인 그래프 알고리즘 중 하나로, 주어진 그래프의 노드들을 서로 다른 집합으로 분리하거나, 두 개의 노드가 같은 집합에 속하는지 여부를 판단하는 데 사용됩니다.

Union-Find 알고리즘의 과정

과정은 총 3단계로 이루어져 있습니다.

Set()

초기화를 담당해주는 함수

union 과 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개의 줄에 걸쳐 숫자쌍이 주어진다. 마지막 줄에는 두 학생이 친구인지 확인하는 숫자쌍이 주어진다.

정리 : 친구관계를 입력받고 친구의 친구면은 친구가 된다..!
입력 예시 : {1, 2} {2, 3} {3, 4} 면은 1,2는 친구, 2,3은 친구, 3,4는 친구일때 2,3이 친구여서 1,4도 친구가 된다. 사람두명을 입력받아서 친구인지 아닌지 판단해주는 문제!

풀이 과정

입력 : 4 3 {1, 2} {2, 3} {3, 4} {1, 4}
4 = 학생 수
3 = 입력받을 갯수({}중괄호당 1개)
마지막 {1, 4}는 확인받고 싶은 친구 관계
출력 : Yes

전체 코드

#include<stdio.h>
 
int n, parent[1001];
 
int Find(int v)
{
    if (parent[v] == v)
        return v;
    else
        return parent[v] = Find(parent[v]);
}
 
void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
 
    if (x != y)
        parent[x] = y;
}
 
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();
 
    for (i = 0; i < m; i++)
    {
        scanf("%d %d", &a, &b);
 
        Union(a, b);
    }
 
    scanf("%d %d", &a, &b);
    if (Find(a) == Find(b))
        printf("YES\n");
    else
        printf("NO\n");
 
    return 0;
}

과정1

//배열을 인덱스의 값으로 초기화 하고있음
void Set(){
	for(int i=0; i<=n; i++){
    	parent[i]=i;
    }
}

부모 배열을 하나 만들어주고 set함수를 이용하여 노드들의 값을 하나의 집합으로 초기화 시켜줍니다.

과정2

void Union(int x, int y){
	x = Find(x);
    y = Find(y);
    
    if(x!=y)
    	parent[x] = y;
}

union 함수로 받은 값들이 원래 있던 값인지 확인해준 후 리턴해줍니다.

과정3

int Find(int v){
	if(parent[v] == v){ //부모와 값이 같다면 그대로 리턴하여 유니온함수의 x,y값 지정
    	return v;
    }
    else{ //부모의 값을 계속 리턴받으며 친구 관계를 확인
    	return parent[v] = Find(parent[v]);
    }
}