[그래프 이론] 알고리즘 개념 : 서로소 집합

이미 배운 내용을 훑어보자

• 그래프 알고리즘은 코테에서 출제 비중이 낮은 편이지만 꼭 제대로 알아야 하는 알고리즘
• 그래프 알고리즘의 한 유형 : DFS/BFS, 최단 경로

 

그래프 자료구조

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

알고리즘 문제에서 '서로 다른 개체(객체)가 연결되어 있다'를 보면 그래프 알고리즘 가장 먼저 떠올리기
ex) 여러 개의 도시가 연결되어 있다

 

트리 자료구조

그래프 자료구조의 일종

부모에서 자식으로 내려오는 계층적인 모델

최소힙 : 트리 자료구조, 항상 부모 노드가 자식 노드보다 크기가 작음

 

	그래프	트리
방향성	방향 그래프 or 무방향 그래프	방향 그래프
순환성	순환 or 비순환	비순환
루트 노드 존재 여부	루트 노드 X	루트 노드 O
노드간 관계성	부모와 자식 관계 없음	부모와 자식 관계
모델의 종류	네트워크 모델	계층 모델

 

그래프 구현 방법

• 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식
• 인접 리스트(Adjacency List) : 리스트를 사용하는 방식

* 두 방식은 메모리와 속도 측면에서 구별되는 특징

 

ex) 노드의 개수 V, 간선의 개수 E인 그래프

• 인접 행렬
  - O(V^2)만큼의 메모리 공간
  - 이어진 간선의 비용 O(1) 시간으로 즉시 알 수 있는 장점
  ex) 플로이드 워셜 알고리즘
        : 모든 노드 → 다른 노드로 가는 최소 비용을 V^2 크기의 2차원 리스트에 저장, 비용 갱신하여 최단거리 계산
• 인접 리스트
  - O(E)만큼의 메모리 공간
  - 이어진 간선의 비용 O(V)만큼의 시간 소요
  ex) 다익스트라 최단 경로 알고리즘
        : 노드의 개수가 V개일 때 V개의 리스트 만들어, 각 노드와 연결된 모든 간선에 대한 정보 리스트에 저장
• 메모리와 시간 염두!
  - 최단 경로문제에서 노드 개수 적으면 플로이드 워셜
  - 노드와 간선 모두 많으면 우선순위 큐 이용하는 다익스트라 알고리즘

 

서로소 집합

수학에서 공통 원소가 없는 두 집합 의미

 

서로소 집합 자료구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

• union-find(합치기 찾기) 자료구조라고도 불림
• 두 집합이 서로소 관계인지 확인할 수 있다
  = 각 집합이 어떤 원소를 공통으로 가지고 있는지를 확인할 수 있다

 

서로소 집합 자료구조는 union과 find 2개의 연산으로 조작

    cf) 스택과 큐는 push(넣기), pop(꺼내기) 연산으로 이루어짐

• union(합집합) 연산 : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
• find(찾기) 연산 : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

 

서로소 집합 자료구조

서로소 집합정보(합집합 연산)가 주어졌을 때, 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘

 

즉, 트리를 이용해 서로소 집합을 계산하는 알고리즘

1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인
       1) A와 B의 루트 노드 A', B'를 각각 찾는다
       2) A'를 B'의 부모 노드로 설정한다(B'가 A'를 가리키도록 한다)
2. 모든 union(합집합) 연산을 처리할 때까지 1의 과정을 반복

* A'와 B' 중 번호 작은 원소가 부모 노드 되도록 구현하는 경우 많음

 

ex) {1, 2, 3, 4, 5, 6} 6개 원소로 구성된 집합에서 union 연산

• union = '같은 집합에 속한다' → 간선으로 표현
• union 관계를 효과적으로 보여주기 위해 그래프 형태로 시각화, 실제로는 트리 자료구조
• 일반적으로 번호 큰 노드가 번호 작은 노드를 가리키도록 트리 구조 이용(번호 작은 노드 부모, 큰 노드 자식)

그래프의 해석

노드 간의 관계 : 전체 원소가 {1, 2, 3, 4}와 {5, 6} 두 집합으로 나뉨. '연결성'

 

알고리즘 동작 원리

• 서로 다른 원소의 합집합(union) 수행할 때,
  각각 루트 노드를 찾아서 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록

0. 노드 개수(V) 크기의 부모 테이블 초기화

• 자기 자신을 부모로 가지도록 설정
• 초기 단계에서는 총 6개의 트리 존재하는 것과 동일

    * 유의사항

    - 부모 테이블은 특정한 노드의 부모에 대해서만 저장
    - 실제 루트를 확인할 때는 재귀적으로 부모 거슬러 올라가서 최종적인 루트 노드 찾기

 

1. union 1, 4

• 노드 1과 노드 4의 루트 노드를 각각 찾기
• 기존 1의 루트 노드 → 1,  4의 루트노드 → 4
• 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정

 

2. union 2, 3

• 노드 2과 노드 3의 루트 노드를 각각 찾기
• 기존 2의 루트 노드 → 2,  3의 루트노드 → 3
• 더 큰 번호에 해당하는 루트 노드 3의 부모를 2로 설정

 

3. union 2, 4

• 노드 2과 노드 4의 루트 노드를 각각 찾기
• 기존 2의 루트 노드 → 2,  4의 루트노드 → 1
• 더 큰 번호에 해당하는 루트 노드 2의 부모를 1로 설정

 

4. union 5, 6

• 노드 5과 노드 6의 루트 노드를 각각 찾기
• 기존 5의 루트 노드 → 5,  6의 루트노드 → 6
• 더 큰 번호에 해당하는 루트 노드 6의 부모를 5로 설정

 

* 유의할 점

- '부모 테이블'을 항상 가지고 있어야 한다

- 루트 노드를 즉시 계산할 수 없고, 부모 테이블을 계속해서 확인하며 거슬러 올라가야 함

 

- 노드 3의 부모노드는 2라고 설정되어 있지만, 노드 2의 부모 노드는 1이기 때문에, 최종적으로 노드 3의 루트 노드는 1

즉, 서로소 집합 알고리즘으로 루트를 찾기 위해서는 재귀적으로 부모를 거슬러 올러가야 함

 

 

# 기본적인 서로소 집합 알고리즘 소스코드

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:    # 아래 초기화에 따라 부모 노드가 자기 자신이면 루트 노드 됨
        return find_parent(parent, parent[x])    
    return x
 
# 두 원소가 속한 집합을 합치기
def union_parent(parent, 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=' ')

 

해석

• 각 원소의 루트 노드가 1, 1, 1, 1, 5, 5
• 루트 노드가 같은 원소끼리는 동일한 집합 → 전체 원소가 {1, 2, 3, 4}와 {5, 6}으로 나누어짐
• find 함수가 비효율적으로 동작(모든 노드 다 확인) → 최악의 경우 시간 복잡도 O(V)     # V는 노드개수

변수 : 노드 개수 V, 간선 개수 E, 부모 테이블 parent

함수 : 루트 노드 찾는 find_parent, 두 원소가 속한 집합 합치는 union_parent

 

* find_parent(부모 테이블 parent , 찾을 원소 x) : 루트 노드 찾음

ㄴ 루트 노드가 아니면 재귀적 호출 : (부모 노드 == 자기 자신) 이면 루트 노드

ㄴ return 루트 노드

 

* union_parent(부모 테이블 parent, 원소 a, 원소 b) : 두 원소가 속한 집합 합침

ㄴ a의 루트 노드 찾기 : find_parent

ㄴ b의 루트 노드 찾기 : find_parent

ㄴ 더 큰 루트 노드를 작은 루트 노드로 바꿈

 

1. 노드 개수 V, 간선 개수 E 입력받기

2. 부모 테이블 parent 초기화 : [0] * (v + 1)

3. 부모 테이블 parent 상에서 부모를 자기 자신으로 초기화

4. union_parent : 각 노드에 대해 수행

5. 각 원소가 속한 집합 출력(루트 노드) : find_parent

6. 각 원소의 부모 테이블 출력 : parent[i]

 

경로 압축 기법을 이용한 최적화

• find .함수를 재귀적으로 호출한 뒤, 부모 테이블값을 갱신
• 각 노드에서 find 함수 호출하면, 루트 노드가 바로 부모 노드가 됨
• 루트 노드에 더욱 빠르게 접근하여 시간 복잡도 개선
• 기존에는 함수가 재귀적으로 호출되어야 해서 시간 복잡도 높았으나, 최적화 이후 곧장 테이블 값에 갱신되어 빨라짐

# 경로 압축 기법 소스코드
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parnet[x]

최적화 전

최적화 후

 

# 개선된 서로소 집합 알고리즘 소스코드

# 특정 원소가 속한 집합을 찾기
# 최적화 ver.
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]
    
# 원본 ver.
def ori_find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return find_parent(parent, parent[x])    
    return x
    
# 두 원소가 속한 집합을 합치기
def union_parent(parent, 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=' ')

 

 

서로소 집합을 활용한 사이클 판별

활용 : 무방향 그래프 내에서 사이클 판별    # cf) 방향 그래프에서는 DFS로 사이클 판별(책 x)

 

알고리즘 동작 원리

• 그래프에 포함되어 있는 간선의 개수가 E일 때, 모든 간선 하나씩 확인
• 매 간선에 대하여 union 및 find 함수를 호출하는 방식
• 간선에 방향성 없는 무향 그래프에서만 적용 가능

 

사이클 판별 알고리즘

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인
   1) 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행
   2) 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것
2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복

 

0. 모든 노드에 대해 자기 자신을 부모로 설정하여 부모 테이블 초기화

 

1. 간선 (1, 2)를 확인

노드 1과 노드 2의 루트 노드는 각각 1과 2

더 큰 번호의 노드 2 부모 노드를 1로 변경

 

2. 간선 (1, 3)을 확인

노드 1과 노드 3의 루트 노드는 각각 1과 3

더 큰 번호의 노드 3 부모 노드를 1로 변경

 

3. 간선 (2, 3)을 확인

노드 2와 노드 3이 이미 루트 노드로 1을 가짐

→ 사이클 발생

 

 

# 서로소 집합을 활용한 사이클 판별 소스코드

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]
    
# 두 원소가 속한 집합을 합치기
def union_parent(parent, 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]
    
cycle = False    # 사이클 발생 여부

for i in range(e):
    a, b = map(int, input().split())
    # 사이클이 발생한 경우 종료
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    # 사이클이 발생하지 않았다면 합집합(union) 수행
    else:
        union_parent(parent, a, b)
        
if cycle:
    print("사이클이 발생했습니다.")
else:
    print("사이클이 발생하지 않았습니다.")

 

해석

 

변수 : 노드 개수 V, 간선 개수 E, 부모 테이블 parent, 사이클 발생 여부 cycle

함수 : 루트 노드 찾는 find_parent, 두 원소가 속한 집합 합치는 union_parent

 

* find_parent(부모 테이블 parent , 찾을 원소 x) : 최적화 ver, 루트 노드 찾음

ㄴ 루트 노드가 아니면 재귀적 호출 : (부모 노드 == 자기 자신) 이면 루트 노드

ㄴ return 루트 노드

 

* union_parent(부모 테이블 parent, 원소 a, 원소 b) : 두 원소가 속한 집합 합침

ㄴ a의 루트 노드 찾기 : find_parent

ㄴ b의 루트 노드 찾기 : find_parent

ㄴ 더 큰 루트 노드를 작은 루트 노드로 바꿈

 

1. 노드 개수 V, 간선 개수 E 입력받기

2. 부모 테이블 parent 초기화 : [0] * (v + 1)

3. 부모 테이블 parent 상에서 부모를 자기 자신으로 초기화

4. 사이클 발생여부 cycle 초기화 : cycle = False

-----------------------------------간선 개수만큼 반복문-----------------------------------

5. 간선 연결된 a, b 입력받기

6. a, b에 대해 루트 노드 찾고, 사이클 판별 : find_parent

ㄴ a, b의 루트 노드가 동일하면 사이클 발생 O : cycle = True

ㄴ a, b의 루트 노드가 달라 사이클 발생 X : union_parent

--------------------------------------------------------------------------------------------------