[Inflearn] 친구인가? (Union & Find 자료구조)(c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

Union Find 자료구조를 처음 들어봐서 구글링으로 좀 찾아보았다.

이게 맞는진 모르겠는데.. 우선 해보자!

우선 입력된 순서쌍의 부모노드의 정보를 배열에 저장해 놓는다.

입력이 아래와 같을 떄,

N=9, M=7 

1 2 

2 3 

3 4 

4 5 

6 7 

7 8 

8 9 

3 8

처음 입력된 1 2 는 먼저 입력된 1로 초기화한다.

1	2	3	4	5	6	7	8	9
1	1

다음 입력된 2 3 을 보자.

2는 부모노드가 정해졌으므로, 패스하고 3번 노드는 부모노드가 정해지지 않았으므로

같이 입력된 2번의 부모 노드를 따라간다.

1	2	3	4	5	6	7	8	9
1	1	1

다음 3 4.

마찬가지로 3은 부모노드가 1이므로, 함께 입력된 4도 3의 부모노드를 따라간다.

 

1	2	3	4	5	6	7	8	9
1	1	1	1

다음 4 5.

4는 부모노드가 1이므로, 함께 입력된 5도 4의 부모노드를 따라간다.

 

1	2	3	4	5	6	7	8	9
1	1	1	1	1

다음 6 7.

6는 부모노드가 정해지지 않았따. 그렇다면 자신을 부모 노드로 지정하고

함께 입력된 7은 6의 부모노드를 따라간다.

 

1	2	3	4	5	6	7	8	9
1	1	1	1	1	6	6

마찬가지로 남은 배열을 채워보자

 

1	2	3	4	5	6	7	8	9
1	1	1	1	1	6	6	6	6

마지막 줄

3번과 8번은 친구인지 확인해보자.

3번은 1번을 부모노드로, 8번은 6번을 부모노드로 가졌으므로

두 번호는 친구가 아닌 것이다.

부모 노드가 다르니깐!

내 머릿속으로 이해한 것을 생각대로 해보았는데 역시나 안 된다..

결국 구글링으로 알게 된 알고리즘대로 구현해보았다.

#. Code

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
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)
{
    freopen("input.txt", "rt", stdin);
 
    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;
}

#. Other code

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
 
int unf[1001];
 
int Find(int v){
    if(v==unf[v]) return v;
    else return unf[v]=Find(unf[v]);
}
 
void Union(int a, int b){
    a=Find(a);
    b=Find(b);
    if(a!=b) unf[a]=b;
}
 
int main(){
    int i, n, m, a, b, fa, fb, j;
 
    scanf("%d %d", &n, &m);
    for(i=1; i<=n; i++){
        unf[i]=i;
    }
 
    for(i=1; i<=m; i++){
        scanf("%d %d", &a, &b);
        Union(a, b);
    }
 
    scanf("%d %d", &a, &b);
    fa=Find(a);
    fb=Find(b);
 
    if(fa==fb) printf("YES\n");
    else printf("NO\n");
 
    return 0;
}

구글의 힘을 얻었으니..

과정을 그려가면서 제대로 이해해보자.

line 24~26) 초기 모든 숫자는 자기 자신과만 집합이 된다. (단독 집합)

1	2	3	4	5	6	7	8	9
1	2	3	4	5	6	7	8	9

line 28~31) 두 수를 입력받고, 두 수를 집합으로 묶어준다.(트리화)

line 14~18) a, b 의 부모 노드를 찾고, 

    return 받은 부모 노드가 다르다면 a 의 부모노드를 b 로 수정한다.

line 9~12) 특정 숫자가 단독 집합이라면, 자기 자신을 return 해준다.

   그렇지 않다면 자신의 부모 노드를 return 해주면서 배열에 부모 노드의 번호를 저장해준다.

입력받은 숫자를 적용해보자.

N=9, M=7 

1 2 

2 3 

3 4 

4 5 

6 7 

7 8 

8 9 

3 8

1, 2 가 입력되었다.

line 17 에 의하여 unf[1] = 2 가 된다.

1	2	3	4	5	6	7	8	9
2	2	3	4	5	6	7	8	9

2, 3 가 입력되었다.

line 17 에 의하여 unf[2] = 3 가 된다.

1	2	3	4	5	6	7	8	9
2	3	3	4	5	6	7	8	9

3, 4 가 입력되었다.

line 17 에 의하여 unf[3] = 4 가 된다.

1	2	3	4	5	6	7	8	9
2	3	4	4	5	6	7	8	9

4, 5 가 입력되었다.

line 17 에 의하여 unf[4] = 5 가 된다.

1	2	3	4	5	6	7	8	9
2	3	4	5	5	6	7	8	9

이 상태에서 Find(1) 이 호출되었다고 해보자.

그렇다면 line 11 에 의해 재귀함수가 동작하게 될 것이다.

아래 그림과 같이 동작하게 되고 

재귀함수에 의해 각 숫자들의 부모노드도 바뀌게 될 것이다.

기존에는 2로 갔다가 3으로 갔다가 4로 갔다가 5에 도착해서 

자신의 부모 노드가 5라는 것을 알았다면

메모라이즈를 활용하여 자신의 부모 노드로 바로 이동할 수 있다는 것이다.

1	2	3	4	5	6	7	8	9
5	5	5	5	5	6	7	8	9

부모 관계를 트리로 그려보면 아래와 같을 것이다.

Union Find 자료구조(?) 알고리즘을 처음 알게 되었는데,

나중에 유용하게 쓰일 수 있을 것 같다.

#. Result

  - Input --------------------------------------------------------

9 7 

1 2 

2 3 

3 4 

4 5 

6 7 

7 8 

8 9 

3 8

------------------------------------------------------------------

  - Output --------------------------------------------------------

NO

------------------------------------------------------------------