알고리즘 소개

분리 집합이란, 아래와 같이 ChatGPT가 소개하고 있다.

"분리 집합"은 수학적인 개념으로, 서로 겹치지 않는 여러 집합들을 의미합니다. 각각의 집합은 다른 집합과 교집합이 없는 상태를 말합니다.

예를 들어, 집합 A와 집합 B가 있다고 가정해보겠습니다. 이 두 집합이 서로 교집합을 가지지 않는다면, 이 두 집합은 분리 집합입니다. 즉, A ∩ B = ∅ (빈 집합)이라면 A와 B는 분리 집합입니다.

분리 집합은 수학적인 이론과 다양한 응용 분야에서 사용될 수 있습니다. 예를 들어 그래프 이론에서는 그래프의 정점들을 분리 집합으로 나누어서 그래프의 특성을 분석하거나 문제를 해결하는 데 활용될 수 있습니다. 또한 집합론, 통계학, 기하학 등 여러 수학 분야에서 분리 집합 개념이 사용됩니다.

정리하자면, 서로 겹치지 않는 여러 집합을 의미하는데 이것을 어떻게 코딩으로 녹여낼까?

이론 및 코드

이론 배경 소개

언제나 그렇듯, 이론보다는 코드로 보면 쉽다.

resp = [ 0 , 1 , 2 , 3 , 4 , 5 ]

위와 같이 배열을 정의하고, 각 원소는 각각의 노드가 연결된 노드의 번호를 의미한다.

초기에는 각각의 노드가 자기 자신만 갖고 있다.

여기서 만약, 1번 노드와 2번 노드가 연결되어 있다면 우리는 아래의 배열과 같이 나타낼수 있을 것이다(일반적으로 대표 노드는 자기 자신의 원소로 둔다).

resp = [ 0 , 1 , 1 , 3 , 4 , 5 ]

그리고 추가로 4번과 5번 노드가 연결되어 있다면 아래와 같을 것이다.

resp = [ 0 , 1 , 1 , 3 , 4 , 4 ]

여기서 헷갈릴만한 점은 어떠한 노드들의 집합을 이야기 할 때, 해당 집합의 대표 노드를 설정해두면 어떠한 노드를 선택했을 때, 대표 노드를 찾아 갈 수 있을 것이다.

대표 노드를 설정하는 방법은 여러개일 수 있다. 위에 보인것 처럶, 자기 자신의 원소를 대표 노드로 설정해둘수 있지만 음수로도 둘 수 있다. 하지만 공통적으로 어떠한 집합의 대표 노드는 해당 집합의 노드 번호가 가장 낮은 것으로 설정하는 것은 변함없다.

다른 포스팅에서는 자기 자신을 대표 노드로 설정해둔게 많아서 이 포스팅에서는 음수로 두는 방법을 보일 것이다.

예를 들기 위해 우리는 새로운 상황을 만들어 볼 것이다. 1번과 2번 노드가 연결되어 있고, 3번과 4번, 5번 노드가 연결 되어있다면 아래의 배열과 같이 보일 것이다.

resp = [ -1 , -1 , 1 , -1 , 3 , 3 ]

여기서 우리는 5번 노드를 고르고 해당 노드가 들어 있는 집합의 대표 노드를 보고 싶다. 그렇게 할 수 있다면 어떠한 2개의 노드를 주어졌을 때 두 노드가 서로 같은 집합에 있는지 없는지 알 수 있기 때문이다.

대표 노드 찾기(find)

5번노드의 값은 3으로 3번 노드를 가르키고 있다. 3번 노드는 음수(대표 노드 의미)이기 때문에 우리는 5번 노드는 3번 노드가 대표 노드로 설정된 집합 안에 있음을 알 수 있다.

이러한 내용을 코드로 보이자면 아래와 같다. 다른 포스팅에서는 재귀함수를 사용했지만, 이해하기 편하기 위해 반복문을 사용했다.

def find(arr, n):
    while arr[n] > 0:
        n = arr[n]
    return n

집합 연결하기(union)

여기까지 이해했다면 3/4는 이해했다고 볼 수 있다.

추가적인 케이스로 만약 두 집합을 합치고 싶은 상황이 발생 했을 때는 어떻게 처리할까?

위의 예시에서는 2,3번노드가 연결되어 있고 4,5,6번 노드가 연결되어 있는데 이 두 집합을 합치는 것을 보일 것이다.

우선 각 집합의 아무 노드를 가져와볼 것이다. 이렇게 가져온 노드를 통해 각각의 집합의 대표 노드를 찾아 보고 두 대표 노드 중 값이 낮은 대표 노드를 합쳐진 집합의 대표노드로 설정해두기 위해 값이 높은 대표 노드의 원소값을 대표 노드 중 값이 낮은 대표 노드 번호로 대체한다. 이렇게 되면 집합이 연결된 것을 볼 수 있다. 아래의 코드를 보자.

def union(arr, node1, node2):
    rep1 = find(arr, node1)
    rep2 = find(arr, node2)
    if rep1 == rep2:
        return
    arr[rep2] = rep1