ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • BoJ 1717 : 집합의 표현
    알고리즘 문제/DFS and Simillar 2017. 10. 29. 19:55

    문제 보기


    기본적으로 Disjoint를 알면 쉬운문제, 근데 애초에 엘리먼트 크기가 1,000,000 이므로 disjoint 말고는 풀수 있는 경우가 딱히 없을듯하다.


    대표적인 Dis-joint set 문제이다. 또는 Union Find 문제라고도 불린다. disjoint 는 집합에서 공통된 원소가 없을 때 두 집합이 disjoint 하다고 표현한다.

    일단 제 포스트보다 더 설명 잘되있는 곳을 소개해드립니다.

    https://ko.wikipedia.org/wiki/%EB%94%94%EC%8A%A4%EC%A1%B0%EC%9D%B8%ED%8A%B8-%EC%85%8B_%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0

    http://koosaga.com/6

    http://www.crocus.co.kr/683


    대충 어떤거냐면, Union Find에서 대충 알수 있듯이... 왠지 Union (합집합) 시키고 Find(찾기) 하는거 같다. 근데 이 구조를 어떤 구조를 이용하냐면, tree 구조를 이용하고, 그 tree 탐색을 하는데 dfs 와 비슷하게 한다. 그래서 분류도 dfs and simillar로 하게되었다.


    우선 두 원소가 지칭 될 때 그 두 원소를 합치는 것이 union 의 역할이다. union의 역할은 하나의 원소의 root(부모)를 찾아서 그 것을 다른 녀석에 연결하는 것이다. 이게 말은 뭐지.. 왜 집합이라했는데 트리구조가 나오니 라면서... 어려울거같은데 함수는 짱짱쉽다. 그리고 집합이 합집합이 된다는게 그냥 하나의 원소를 루트로 잡고 그 하나 주위로 다 자식으로 붙이면 되는것이 개념적으로 쉽기 때문이다. 

    find(n) 을 n원소의 root 원소를 찾는다고하자. 두 원소가 x, y 일 경우 y가 속한 집합을 x가 속한 집합에 포함시킨다고 하자. 스도코드는 이럴것이다.

     find(y).child = find(x);

    그러니까 y가 속한 집합의 root부모 의 자식으로 x가 속한 집합의 root부모 만 넣어주면 자연스레 x가 원래 포함하고 있는 모든 원소들이 y가 속한 집합으로 포함되게 되는것이다. 또 반대로는 이렇게도 표현할 수 있을것이다.

    find(x).parent = find(y); 이거는 x의 root를 찾아 그 것의 부모를 y의 root로 만든다는 것이다. 그게그거다... (사실은 집합을 합친다는 것이 우리가 할것인건데, 트리를 합친다고 표현하는게 쉬우니까... 그게 바로 disjoint set, union find, 트리 구조다.)

    설명하다보니 union과 find 다 설명하게되었다.


    일단 우리는 parent 배열을 생성하고, 각 원소의 parent를 자기 자신으로 설정해준다. 

    우리가 설명한 find 함수는 다음과 같이 생겼다. 코드가 짧아서 구냥 다올려보았다.

    find함수는 재귀적으로 탐색하며 자신의 부모를 찾아서 내려간다. 이 부분이 dfs와 닮았다.

    다음 배열을 확인해보자

    parent 배열

    1 2 3 4 5

    5 4 1 4 5 

    그렇담 이렇게 되있는 것이다.

    (parent) 5 -  1 - 3  (child)

    (parent) 4 - 2   (child)

    find (3)은 어떻게 동작하나? 최종 부모인 5를 반환한다.

    find (3){

    else return find(parent[3]==1){

    else return find(parent[1]==5){

    <-------- return 5


    a 와 b를 union 하는 과정은 다음과 같다. 

    parent[find(a)]=find(b)   a의 root의 root를 b의 root로 두는것이다. 

    parent 배열

    1 2 3 4 5

    5 4 1 4 5

    (parent) 5 -  1 - 3  (child)

    (parent) 4 - 2   (child)

    인 상태에서 1이 포함된 집합을 2가 포함된 집합과 합친다고 해보자.

    1의 root를 찾아서 "find(1)"  그녀석의 parent를  "parent[find(1)]" 바로 원소 2의 root "find(2)"로 설정한다.


    그렇담 parent 배열은 다음과같이된다.

    parent 배열

    1 2 3 4 5

    5 4 1 4 4

    (parent) 4 - 2
                 + 5 - 1 - 3 (child)

    그렇담 3의 부모를 찾는 find 함수는 몇번 호출될까 다음을 확인하자.


    find(3){

    else return find(parent[3]==1){

    else return find(parent[1]==5){

    else return find(parent[5]==4){

    <--------------return 4;


    꽤 깊어졌다. 3번이나 내려가다니, 자신의 부모의 부모가나올떄까지 부르니까.... 최대 함수는 n-1깊이 만큼 깊어질 수 있을것이다. BoJ의 엘리먼트 백만개 * 십만개 = 천억.... 1천초...그러니까 제한 시간내에 푸는 것은 꿈도 못꾼다.


    애초에 paarent를 주루루룩 연결할 필요가있을까? 우리는 한 집합이 표현되었다는것을 그 연결된 원소들이 단 하나의 root를 가지게만 만들면 되는것이니까. find 함수를 다음과 같이 바꾸면....


     자기가 한 집합의 root 원소가 아니라면 자신을 포함한 모든 parent 까지 거슬러 올라가 자기가 속한 집합을 대표하는 root 까지 도달하는데, 자기 자신을 포함한 거슬러 올라갔던 parent들의 부모를 대표 원소 root로 갱신하게된다.

    예를 살펴보자. 다음과 같은 구조가 생길 수 있다.
    prent 배열
    1 2 3 4 5
    1 4 1 4 5

    (parent) 1 - 3  (child)
    (parent) 4 - 2
    (parent) 5

    여기서 1이 속한 집합을 5집합과 합쳐보쟈

    parent[ufind(1)]= ufind(5);

    ufind(1) {return 1;} ufind(5){ return 5}
    parent[1] = 5; 

    // 이런 명제는 이전 find 함수와 동작이 같다. 왜냐면 두 원소 모두 부모 원소가 존재하지 않기떄문이다. 즉, 자기 자신이 집합을 대표하는 root 원소이기 떄문이다.

    다음 명제에서 우리는 확연한 차이를 볼 수 있다.

    현재 parent 배열
    1 2 3 4 5
    5 4 1 4 5

    (parent) 5 - 1 - 3 (child)
               4 - 2 

    자 여기서 3이 속한 집합을 2가 속한 집합과 합쳐보쟈

    parent[ufind(3)] = ufind(2);

    ufind(3){

    else return parent[3]=ufind(parent[3]==1){

            else return parent[1]=ufind(parent[1]==5){

    parent[3],[1](갱신) < return 5;

    ufind(2){

    else return parent[2]=ufind(parent[2]==4){

    parent[2](갱신) < return 4;

    parent 배열

    1 2 3 4 5
    5 4 5 4 4

    (parent) 4 - 2
                 + 5 - 1
     + 3
    3의 원소가 5 바로 밑의 자식이 된것을 확인될 수 있다.

    자 여기서 3의 원소와 원소 5가 같은 집합인지 확인해보자

    ufind(3) == ufind(5)?

    ufind(3){

    else return parent[3]=ufind(parent[3]==5){

            else return parent[5]=ufind(parent[5]==4){

    parent[3],[5](갱신) < return 4;

    ufind(5){

    else return parent[5]=ufind(parent[5]==4){

    parent[5] (갱신) < return 4;

    ufind(3)== ufind(5) is true

    그러나 우리가 보고싶은것은 아래의 

    parent 배열
    1 2 3 4 5
    5 4 4 4 4

    (parent) 4 - 2        (child)
      + 5 - 1
      + 3

    이 녀석들이다. 3은 한번 더 위로 올라와서 4바로 밑의 자식으로 붙어버렸다. 이렇게 되도 상관없다. 우리는 자식과 부모를 따지려는게 아니라 한 집합을 표현하기위해 트리로 묶는 구조를 이용했기 때문에, tree가 더 깊이 내려가지 않고 높이가 좀 더 줄으면 줄을 수록 연산속도에 더 좋은것이다.

    이 union find tree의 재귀 구조는 어디까지 줄어들수 있을까? 당연히 높이 1까지 줄어들수 있다. 다음과 같다.

    4  - 2
       + 5
       + 3
       + 1 

    신기하다. 

    어떤 초기 원소가 자기 자신이 한 집합을 대표하는 root가 아니라면 자신의 parent 를 항상 호출하며 갱신하는데 그것도 root가 아니라면 parent의 parent를 찾고 또 그것이 root까지 올라가 결국 초기 원소를 포함한 그 것의 모든 parent를 root로 갱신하는 것이다. 단 초기 원소의 자식은 아니고...

    ufind 함수가 해당 녀석이 포함된 집합 ( 정확하게는 그 집합을 대표하는 root 원소)를 반환할 때마다, 그 녀석, 그리고 그녀석의 parent, 그리고 그 parent의 parent, 또 그 parent의 parent... 계속해서 결국 root 원소까지 나올때까지 그 들의 parent를 현재 root로 갱신한다. 

     

    말이 베베꼬였는데, 어쨌든, "지가 한집합을 대표하는 root가 아니면, root 까지 거슬러 올라가고 그 거처간 녀석들의 parent를 root로 갱신한다 그래서 결국 집합을 표현하는 root의 깊이가 져낸 짧아진다 최대 높이가 1까지 줄어든다." 소스는 더 쉽다.


    소스보기


    '알고리즘 문제 > DFS and Simillar' 카테고리의 다른 글

    백준 12784 인하니카 공화국  (0) 2018.05.29
    백준 2447 별찍기10  (0) 2018.03.06
    884C Bertown Subway  (0) 2017.11.05
    BoJ 1717 : 집합의 표현  (0) 2017.10.29

    댓글 0

Designed by Tistory.