다양한 그래프 알고리즘 - 서로소 집합

안녕하세요. 오늘은 코딩 테스트에서 사용할 수 있는 다양한 그래프 알고리즘에 대해서 소개드리려고합니다.

그래프 알고리즘에 들어가기 앞서, 먼저 기초 내용부터 다지고 들어가겠습니다.

 

그래프

 

노드와 노드 사이에 연결된 간선정보를 가지고 있는 자료구조를 의미합니다.

그래서 알고리즘 문제에서 '서로 다른 개체(혹은 객체)가 연결되어 있다'는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 합니다.

 

 

트리

 

더불어 그래프 자료구조 중에서 트리 자료구조는 다양한 알고리즘에서 사용되므로 꼭 기억하면 좋습니다.

 

다익스트라 최단 경로 알고리즘에서는 우선순위 큐가 사용되었는데, 우선순위 큐를 구현하기 위해 최소 힙이나 최대 힙을 이용할 수 있다고 했습니다.

 

최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속합니다.

트리 자료구조는 부모에서 자식으로 내려오는 계층적인 모델에 속합니다.

 

 

그래프와 트리 비교

기준	그래프	트리
방향성	방향 그래프와 무방향 그래프 모두 가능	주로 무방향 그래프
순환성	순환이 발생할 수 있음	순환 없음(비순환)
루트 노드 존재 여부	루트 노드 없음	하나의 루트 노드 존재
노드간 관계	노드 간에 양방향 또는 단방향 관계 가능	부모-자식 관계(단방향)
모델의 종류	다양한 응용 분야에서 사용가능 (소셜네트워크, 도로망, 등)	계층 구조, 계층적 데이터 구조

 

알아두어야 할 점은 어떤 문제를 만나든 메모리와 시간을 염두에 두고 알고리즘을 선택해서 구현해야 하는 것입니다.

예를 들어, 최단 경로를 찾아야 하는 문제가 출제되었을 때, 노드의 개수가 적은 경우에는 플로이드 워셜 알고리즘을 이용할 수 있다. 반면에 노드와 간선의 개수가 모두 많으면 우선순위 큐를 이용하는 다익스트라 알고리즘을 이용하면 유리합니다.

 

 

서로소 집합

 

수학에서 서로소 집합이란  공통 원소가 없는 두 집합을 의미합니다.

예를 들어 집합 { 1, 2 }  와 집합 { 3, 4 } 는 서로소 관계입니다. 반면에 { 1, 2 } , { 2, 3 } 은 2라는 원소가 두 집합에 공통적으로 포함되어 있기 때문에 서로소 관계가 아닙니다.

 

서로소 집합 자료구조는 여러 원소들을 그룹화하고 관리하기 위한 자료구조입니다. 

각 원소는 자신이 속한 그룹을 나타내며, 이 그룹은 다른 그룹과 겹치지 않아야 합니다. 

이 자료구조는 주로 두 가지 연산을 제공하며, 이를 통해 그룹을 합치거나 그룹의 대표자를 찾을 수 있습니다.

 

 

 

1. MakeSet(x, y): 새로운 원소를 하나의 그룹으로 생성합니다. 각 원소는 자신을 대표하는 대표자(또는 부모)를 가집니다. 처음에는 모든 원소가 자신만을 포함하는 그룹을 갖습니다.

 

2. Find(x): 어떤 원소가 속한 그룹의 대표자(부모)를 찾습니다. 이 과정에서 그룹 내 모든 원소의 대표자를 업데이트하며, 이를 경로 압축이라고 합니다. Find 연산을 사용하여 원소가 속한 그룹을 식별합니다.

 

3. Union(x, y): 두 원소 x와 y가 속한 두 그룹을 합칩니다. 이 연산은 두 그룹을 하나로 합치고, 하나의 그룹을 다른 그룹의 대표자(부모)로 설정합니다.

 

 

서로소 집합 자료구조는 주로 그래프 알고리즘에서 사이클 검출이나 최소 신장 트리(MST)를 구성하는 데 사용됩니다. 

 

예를 들어, 크루스칼 알고리즘에서 서로소 집합 자료구조를 사용하여 그래프 내의 간선들을 연결하면서 사이클을 검출하고 최소 신장 트리를 만듭니다. 

 

이를 통해 최소 비용으로 그래프를 연결할 수 있습니다.

 

 

 

 

서로소 집합 자료구조의 핵심 연산인 합집합(Union)과 찾기(Find)의 계산 과정

 

union ( 합집합 ) 연산을 화긴하여, 서로 연결된 두 노드 A, B를 확인합니다.

• A와 B의 루트 노드 A' , B' 를 각각 찾습니다.
• A' 를 B'의 부모 노드로 설정합니다.(B'가 A'를 가리키도록 합니다.)

모든 union (합집합) 연산을 처리할 때까지 1번 과정을 반복합니다.

 

 

예시

 

이해를 돕기 위해 전체 집합 {1, 2, 3, 4, 5, 6}로 시작하고, 서로소 집합 계산 알고리즘을 통해 UNION 연산을 적용하는 과정을 단계별로 설명하겠습니다.

 

여러한 4개의 union 연산은 각각 '1과 4는 같은 집합' , '2와 3은 같은 집합' .... 이라는 의미를 가지고 있습니다.

다시 말해 총 4개의 union 연산이 존재하는 것입니다.

 

이때 4개의 union 연산이 수행된 후에, 전체 원소들이 결과적으로 어떠한 형태의 부분 집합으로 나누어질지 확인해봐야합니다.

 

이러한 4개의 union 연산들은 그래프 형태로 표현될 수도 있습니다.

 

즉, 6개의 노드가 있고 4개의 간선이 존재하는 그래프로 바꾸어서 생각할 수 있습니다.

 

 

초기상태

Node: 1 2 3 4 5 6
Parent: 1 2 3 4 5 6

 

union(1, 4)
Find(1)과 Find(4)를 통해 각각의 대표자를 찾습니다.
Find(1)은 1을 반환합니다.
Find(4)는 4를 반환합니다.
대표자 1과 대표자 4 중 하나를 다른 대표자의 부모로 설정합니다. 이 경우, 1의 부모를 4로 설정하거나 4의 부모를 1로 설정해도 상관 없습니다. 여기서는 1을 4의 부모로 설정합니다.
연결 후 상태:
{1, 4}, {2}, {3}, {5}, {6}

Node: 1 2 3 4 5 6
Parent: 1 2 3 1 5 6

 

 

union(2, 3)
Find(2)와 Find(3)을 통해 각각의 대표자를 찾습니다.
Find(2)는 1을 반환합니다. (1은 이전 연산에서 4의 부모로 설정됨)
Find(3)은 3을 반환합니다.
대표자 1과 대표자 3 중 하나를 다른 대표자의 부모로 설정합니다. 이 경우, 1의 부모를 3으로 설정하거나 3의 부모를 1로 설정해도 상관 없습니다. 여기서는 1을 3의 부모로 설정합니다.
연결 후 상태:
{1, 4}, {2, 3}, {5}, {6}

Node: 1 2 3 4 5 6
Parent: 1 2 2 1 5 6

 

union(2, 4)
Find(2)와 Find(4)를 통해 각각의 대표자를 찾습니다.
Find(2)는 3을 반환합니다. (이전 연산에서 1이 3의 부모로 설정됨)
Find(4)는 1을 반환합니다. (1은 이전 연산에서 4의 부모로 설정됨)
대표자 3와 대표자 1 중 하나를 다른 대표자의 부모로 설정합니다. 이 경우, 3의 부모를 1로 설정하거나 1의 부모를 3으로 설정해도 상관 없습니다. 여기서는 3을 1의 부모로 설정합니다.
연결 후 상태:
{1, 2, 3, 4}, {5}, {6}

Node: 1 2 3 4 5 6
Parent: 1 1 2 1 5 6

 

 

union(5, 6)
Find(5)와 Find(6)을 통해 각각의 대표자를 찾습니다.
Find(5)는 5를 반환합니다.
Find(6)는 6을 반환합니다.
대표자 5와 대표자 6 중 하나를 다른 대표자의 부모로 설정합니다. 이 경우, 5의 부모를 6으로 설정하거나 6의 부모를 5로 설정해도 상관 없습니다. 여기서는 5를 6의 부모로 설정합니다.
연결 후 상태:
{1, 2, 3, 4}, {5, 6}

Node: 1 2 3 4 5 6
Parent: 1 1 2 1 5 5

 

이제 각각의 집합은 서로소입니다. 각 집합은 하나의 그룹으로 연결되었고, 대표자를 통해 각 집합을 식별할 수 있습니다. 이것이 서로소 집합 계산 알고리즘의 동작 방식입니다.

 

 

 

서로소 집합 알고리즘 소스코드

# 특정 원소가 속한 집합을 찾는 함수
def find_parent(parent, x):
    # 만약 현재 원소 x가 자기 자신을 가리키지 않는다면,
    if parent[x] != x:
        # 루트 노드를 찾을 때까지 재귀 호출하여 부모를 업데이트한다.
        return find_parent(parent, parent[x])
    # 루트 노드에 도달하면 그 값을 반환한다.
    return x

# 두 원소가 속한 집합을 합치는 함수
def union_parent(parent, a, b):
    # 각 원소 a와 b의 루트 노드를 찾는다.
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    # 작은 루트 노드를 가진 쪽을 큰 루트 노드를 가진 쪽의 자식으로 합친다.
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1)  # 부모 테이블 초기화하기

# 부모 테이블상에서, 각 노드의 부모를 자기 자신으로 초기화한다.
for i in range(1, v + 1):
    parent[i] = i

# Union 연산을 각각 수행
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력하기
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
    print(find_parent(parent, i), end=' ')

print()

# 부모 테이블 내용 출력하기
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')

 

입력예시

6 4
1 4
2 3
2 4
5 6

 

1단계

 

먼저, 입력으로 노드의 개수(v)와 간선(Union 연산)의 개수(e)를 받습니다. 이 예시에서는 노드가 6개이고 간선이 4개입니다.

# 노드의 개수(v)와 간선(Union 연산)의 개수(e) 입력 받기
v, e = map(int, input().split())

 

 

2단계

 

부모 테이블(parent)을 초기화합니다.

# 부모 테이블(parent)을 초기화하기
parent = [0] * (v + 1)
for i in range(1, v + 1):
    parent[i] = i

 

부모 테이블은 각 노드의 부모를 나타내는 배열로, 초기에는 각 노드가 자기 자신을 가리키도록 초기화됩니다.

즉, parent=[1, 2, 3, 4, 5, 6] 이 됩니다.

 

 

3단계

 

입력으로 주이진 간선의 정보를 통해 Union 연산을 수행합니다.

 

입력 : 1, 4

• a, b는 각각 1과 4입니다.
• find_parent(parent, 1) 은 1의 루트 노드를 찾아 1을 반환합니다.
• find_parent(parent, 4) 는 4의 루트 노드를 찾아 4를 반환합니다.
• 1과 4를 합칠 때, 1이 4보다 작으므로 4의 부모를 1로 설정합니다. 따라서, parent = [1, 2, 3, 1, 5, 6]

이와 같은 방식으로 나머지 간선에 대해서도 Union 연산을 수행합니다.

# 입력으로 주어진 간선의 정보를 통해 Union 연산 수행하기
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)  # 이 코드는 이미 주어진 함수에서 구현되어 있습니다.

 

 

4단계

각 원소가 속한 집합을 출력합니다. 이때, find_parent 함수를 사용하여 각 노드의 루트 노드를 찾아 출력합니다.

출력 결과는 다음과 같습니다. 각 원소가 속한 집합 : 1 2 2 1 5 5

# 각 원소가 속한 집합 출력하기
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
    print(find_parent(parent, i), end=' ')
print()

 

 

5단계

부모 테이블을 출력합니다. 부모 테이블은 각 노드의 부모를 나타내며, 각 원소가 속한 집합을 표현합니다.

출력 결과는 다음과 같습니다. 부모 테이블 1 2 3 1 5 6

# 부모 테이블 내용 출력하기
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')

 

다음은 입력 2, 3...

이렇게 서로소 집합을 구현하고 간선의 연결 정보를 통해 집합을 합치는 과정을 통해 그래프의 연결 여부를 판단하거나 최소 신장 트리를 구할 수 있습니다.

 

결과