[Union Find] 정의 및 기본 예제

 

Union Find는 각각의 독립된 데이터를 그룹화시켜서 관리할 때 사용하는 자료구조이다. 

 

예를 들어서, A, B, C, D, E, F 이런 데이터가 있다고 해보자. 이들은 각각의 독립된 데이터들이다. 얘네에 해당하는 배열도 하나 만들자. 그리고 각각 0으로 채운다. 여기서 0의 의미는 A,B,C,D,E,F가 어디에도 속하지 않은 독립적인 데이터라는 뜻이다. (1인 기업 이런 것처럼)

 

얘네들은 그룹화를 시킬 것이다. Union('A','B')이렇게 하면 A,B가 하나의 그룹이 되어버린다. 그리고 여기에서 설명상 앞에 있는 애를 리더로 잡고 설명하겠다. A, B가 그룹화가 되면 보스는 A가 될 것이다. B에 해당하는 인덱스에 A라고 적어줄 것이다. 이렇게 A, B 그룹이 되었을 때 보스는 어떤 사람으로 정하든 관련이 없지만. 여기서는 편의상 A가 보스라고 가정하자. A가 속한 그룹의 보스는 A 자기자신이니까 그냥 0으로 두면 된다.

​

보스는 0으로 체크, 자기 자신이 보스 라고 하면 0이고 보스가 아니면 다른 값이 적혀져있을 것이다. Union('D','E') 이렇게 하면 E의 보스를 D라고 적어주면 된다. Union('B','E') 이럴 경우에는 A학교랑 B학교랑 패싸움을 한다고 해보자. 그러면 다 싸울 필요 없이 각 그룹의 대빵만 나와서 싸우면 된다. AB 그룹의 대빵은 A이고, DE그룹의 대빵은 D이다. 싸움에서 A가 이겼다고 가정하자. 그러면 D자리에 그냥 AB그룹의 보스인 A를 적어주면 된다. 다 싸울 필요 없이 Boss끼리 싸우면 된다. 가 학교가 이기면 나 학교 애들이 다 들어감. 그래서 E가 속한 그룹이 B가 속한 그룹으로 들어가게 된다. 그러면 각각의 보스를 찾은 다음에 보스를 밑으로 넣어주면 된다. 이렇게 하면 그룹화가 다 이루어지고 결국 A가 보스가 된다.

​

다음 Union('B','D')B의 보스는 A, D의 보스는 A. 둘이 보스가 같다고 하면 Union이 안된다. 이미 같은 그룹이라서. 그러면 그냥 꺼버리면 된다. Union('D','F') 를 하자고 하면 D가 속한 그룹의 보스는 A이다. F가 속한 그룹의 보스는 F 자기자신이다. 그러면 F의 보스 위치에 A를 적어주면 된다. 이렇게 독립화된 데이터를 group화해서 관리할 때 사용하는 것이 Union Find이다. 각각의 보스를 먼저 찾은 다음에 보스가 같으면 끄고, 보스가 다르면 한쪽으로 넣는다.

---

 

Ex) A ~ F 사이의 문자 2개를 입력받은 뒤, 이 문자들이 같은 그룹인지 다른 그룹인지 출력해주세요.

단, union('A','B') / union('D','E') / union('B','E') / union('B','D') / union('D','F')의 과정을 거쳤습니다. 

 

▷ 간결한 코드 

# Union Find

arr = [0]*200

def findboss(member):
    global arr
    if arr[ord(member)] == 0:
        return member
    else:
        ret = findboss(arr[ord(member)])
    return ret

def union(a,b):
    global arr
    boss_of_a = findboss(a)
    boss_of_b = findboss(b)
    if boss_of_a == boss_of_b:
        return
    else:
        arr[ord(boss_of_b)] = boss_of_a

union('A','B')
union('D','E')
union('B','E')
union('B','D')
union('D','F')

member1, member2 = input().split()
if findboss(member1) == findboss(member2):
    print("같은 그룹")
else:
    print("다른 그룹")

 

▷ 해설이 있는 코드

# Union Find

# 아스키 코드 값을 넣어주기 위해 충분히 크게 만들어 줌
arr = [0]*200

def findboss(member):
    global arr
    # 값이 0이면 자기가 보스라는 뜻
    if arr[ord(member)] == 0:
        return member
    else:
        # 값에 적혀있는 멤버를 또 넣어줌
        # 그러면 자기가 보스인 사람이 나올 때까지 계속 돌게 됨
        ret = findboss(arr[ord(member)])
    return ret

def union(a,b):
    global arr
    boss_of_a = findboss(a)
    boss_of_b = findboss(b)
    # 보스가 같으면 이미 같은 그룹이니까 off
    if boss_of_a == boss_of_b:
        return
    # 보스가 다르다면 b가 속한 그룹의 boss를 a가 속한 그룹의 boss 밑으로 넣기
    else:
        arr[ord(boss_of_b)] = boss_of_a

union('A','B')
union('D','E')
union('B','E')
union('B','D')
union('D','F')

member1, member2 = input().split()
if findboss(member1) == findboss(member2):
    print("같은 그룹")
else:
    print("다른 그룹")