Union-Find(Disjoint-Set) 에 대해, + BOJ 4195

안녕하세요 원재입니다 ^ㅡ^ 이번에는 알고리즘에서 주로 쓰이는 (특히 그래프 알고리즘) Union-Find 에 대해서 알아보려고 합니다!

Union-Find 는?

Union-Find 의 가벼운 첫 인상을 알려드리자면, Union-Find 는 우리 조상님 찾기 라고 볼 수 있습니다!

조상님이라고 부르세요

위와 같은 그래프가 있다고 생각해 봅시다. 루트 노드는 1 과 5 가 되겠죠? 3,4 를 자식으로 가지는 1번 트리와, 6, 2를 자식으로 가지는 5번 트리가 존재한다고 생각하겠습니다. 그렇다면 우리는 Union-Find 를 통해 4의 조상님은 1이에요! 라는 것을 Find 할 수 있습니다.

그렇다면 Union 은 어떨때 사용할까요? 바로 족보 구매 입니다.

족보입니다

만약 위와 같은 노드에서 5번 노드가 3번 노드에 Union, 즉 합쳐지게 된다면 어떻게 될까요? 5번 노드를 조상으로 가지고 있던 아래 노드들뿐만 아니라 5번 노드까지 1번 노드를 루트 노드, 즉 조상으로 가지게 됩니다!

이렇게 노드들이 합쳐지고, 노드의 조상을 갱신까지 하는 것이 우리가 사용할 Union 이라고 볼 수 있겠습니다! 그렇다면 어떻게 구현하는지 직접 코드를 보면서 알아보도록 해볼까요? ^ㅡ^

Union-find 구현 (Python Code)

1. find(x)

def find(x):
    if x == parent[x]:
        return x
    else:
        return find(parent[x])

find(x) 의 경우 말 그대로 x 의 조상을 찾는 코드입니다. 여기서 parent 는 루트 노드가 무엇인지 담겨있는 배열이라고만 일단 생각해주세요.

def find(x):
    if x == parent[x]:
        return x

위 사진의 1번 노드와 같이 자기 자신이 조상인 경우에는 바로 return 을 해줘야 합니다! 또한 이 코드는 재귀를 통해 조상을 찾는 데에도 사용됩니다.

    else:
        return find(parent[x])

조상을 찾지 못했을 경우에 실행되는 코드입니다! 재귀 호출을 통해 다시 find 를 호출 하면서 조상을 찾을때까지 실행된다고 볼 수 있습니다. 짧은 코드이니 이해하기 쉬우실거라 생각합니다.

2. union(x, y)

def union(x, y):
    x = find(x)
    y = find(y)

    if x != y:
        parent[y] = x

union 의 경우 노드를 합쳐 조상을 갱신하는 코드입니다. union 할 x, y 값을 인자로 받아 find 함수를 통해 조상을 찾아주고, 만약 서로 조상이 같지 않다면 루트 노드를 갱신해주는 코드입니다. 마찬가지로 그렇게 어렵지 않은 코드이니 쉽게 이해하실 수 있을거라 생각합니다.

Union-Find 를 통한 문제 풀이

https://www.acmicpc.net/problem/4195

백준의 친구 네트워크 라는 문제입니다. 두 사람의 네트워크에는 몇 명의 친구가 있는지를 구하는 문제입니다. 두 사람의 이름이 주어지면, 서로 친구로 추가해주고 (Union) 서로 연결되있는 조상을 찾은 후 (find) 에 조상에게 연결된 노드의 갯수를 리턴하면 되는 문제입니다.

해시를 통해 검색 속도를 높일 수 있으므로 python 의 딕셔너리를 사용해서 푸는것이 좋은 문제였습니다! 아래 코드와 함께 설명 주석을 달아 놓았습니다. 이해하기 편하실겁니다 데헷

def find(x): 
    if x == parent[x]:
        return x
    else:
        p = find(parent[x])
        parent[x] = p
        return parent[x]

def union(x, y):
    x = find(x)
    y = find(y)
    if x != y:
        parent[y] = x
        # number 딕셔너리를 통해 친구 수를 저장합니다.
        number[x] += number[y]

test_case = int(input())

for _ in range(test_case):
    f = int(input())
    # dictionary 를 통해 해시 사용이 가능합니다!
    parent = dict()
    number = dict()

    for _ in range(f):
          # 두 명의 친구를 공백을 기준으로 입력받습니다.
        x, y = input().split(' ')
        # 만약 아직 parent 에 들어가있지 않은 상태라면, 스스로를 조상으로 체크!
        # 친구 수도 마찬가지로 1로 놓습니다!
        if x not in parent:
            parent[x] = x
            number[x] = 1
        if y not in parent:
            parent[y] = y
            number[y] = 1
        # 서로 union 해줍니다.
        union(x, y)
        print(number[find(x)])

마치며

이번에는 그래프에서 자주 사용하는 Union-Find 에 대해 알아봤습니다. 재귀를 처음 접하시거나 그래프가 낯선 분들에게는 조금 어려울 수도 있는 구조라고 생각합니다. 하지만 천천히 조금씩 앞으로 나아가다보면 완벽하게 이해하고 잘 응용할 수 있을 거라 믿습니다! 오늘도 빠이띵!