2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/알고리즘

[알고리즘]Union Find

원당컴1 2022. 6. 9. 20:53
유니온파인드(Union Find)란

- 대표적인 그래프 알고리즘으로 합집합 찾기 라는 의미를 가지고 있다.

- 상호배타적집합(Disjoint-set) 이라고도 한다.

- 여러개의 노드가 있을때 두개의 노드가 같은 그래프에 속하는지 판별하는 알고리즘

- 2가지 연산으로 이루어져 있다.

단계 1. 주어진 원소들이 서로 같은 집합에 속하는가를 알아내고(Find)
단계 2. 만약에 그렇지 않으면 같은 집합에 속하도록 추가하라(Union)

 

유니온파인드 구현방법

예)

위와 같은 경우 union(1,5),union(4,5),union(2,3),union(2,7),union(3,7),union(6,7) 을 표현한 그래프
이러한 그래프에 connected component 는 {0},{1,4,5},{2,3,6,7} 이렇게 3개의 그룹으로 나뉜다

여기에 2와 5를 연결해 보자

Union(2,5)를 수행한 모습

 

구현하는 방법은 다음과 같다.

1단계) 각 ID 에 그룹 번호를 자신의 ID로 그룹 번호 결정

2단계) union(1,5) 를 수행하기 위해서 Find(1)=1 과 Find(5)=5 의 서로 다른 그룹을 같게 만든다.

3단계) union(4,5) 를 수행하기 위해서 Find(4)=4 과 Find(5)=1 의 서로 다른 그룹을 같게 만든다.

이때 Find(5) 에서 1을 찾는 규칙은 다음과 같다.

Find(5)->Find(1) 에서 찾고자 하는 자신의 번호와 그룹의 번호가 같으면 해당 번호가 자기 그룹이기 때문에 그룹번호를 리턴한다.

4단계) union(2,3) 를 수행하기 위해서 Find(2)=2 과 Find(3)=3 의 서로 다른 그룹을 같게 만든다.

5단계) union(2,7) 를 수행하기 위해서 Find(2)=2 과 Find(7)=7 의 서로 다른 그룹을 같게 만든다.

5단계) union(3,7) 를 수행하기 위해서 Find(3)=2 과 Find(7)=2 에서 이미 같은 그룹이기 때문에 굳이 union을 수행할 필요가 없다.

6단계) union(6,7) 를 수행하기 위해서 Find(6)=6 과 Find(7)=2 의 서로 다른 그룹을 같게 만든다.

6단계가 끝나면  {0},{1,4,5},{2,3,6,7}  이러한 모습이 된다.

7단계) union(2,5)를 수행하기 위해서 find(2)=2,find(5)=1 이기 때문에 서로 다른 그룹을 같게 만들면 다음과 같은 형태가 된다.

위와 같이 되는데 여기서 Find(6)=1 이 되는 원리는 Find(6)->Find(2)->Find(1)을 찾아가기 때문에 Find(6)=1 이 나오게 된다.

 

문제풀이

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2265&sca=60&s1=&s2=&s3=&s4=

이문제는 모두 끊어져 있다고 생각하고 뒤에서 부터 삭제 명령이 들어 왔다면 이어주면 되는 Union Find 형태의 알고리즘 유형이다.

 

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <stdio.h>
 
using namespace std;
 
#define MAXN 200200
 
int N,Q;
int parent[MAXN],group[MAXN],q[MAXN*2][3],ans[MAXN*2];
 
int find(int node)
{
    if(node!=group[node]) group[node]=find(group[node]);
    return group[node];
}
 
int main()
{
    int i;
    //freopen("input.txt","r",stdin);
    scanf("%d %d",&N,&Q);
    Q+=N-1;
   group[1]=1;
    for(i=2;i<=N;i++)
    {
        scanf("%d",&parent[i]);
       group[i]=i;
    }
    for(i=1;i<=Q;i++)
    {
        scanf("%d %d",&q[i][0],&q[i][1]);
        if(q[i][0]==1scanf("%d",&q[i][2]);
    }
    for(i=Q;i>=1;i--)
    {
        if(q[i][0]==0) group[q[i][1]]=parent[q[i][1]];
        else if(find(group[q[i][1]])==find(group[q[i][2]])) ans[i]=1;
    }
    for(i=1;i<Q;i++)
    {
        if(q[i][0]==0continue;
        if(ans[i]==1printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}
cs
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기