🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다.
이번 포스팅에서는 그래프 알고리즘 종류 중 하나라고 할 수 있는 서로소 집합 자료구조를 활용한 알고리즘에 대해 알아보려고 한다. 책에서 소개하는 그래프 알고리즘 종류로는 그리디 알고리즘이라고도 할 수 있는 크루스칼 알고리즘과 스택과 큐를 활용해야 하는 위상 정렬 알고리즘이 있다. 이러한 알고리즘을 배우기에 앞서 책에서 가장 먼저 소개하는 서로소 집합 자료구조에 대해 배워보고 주어진 그래프 데이터를 기반으로 서로소 집합을 어떻게 알아낼 수 있는지 구현 소스코드도 살펴보자.
우선 간선과 노드로 이루어져 있는 그래프 데이터들은 우리가 저번까지 배웠던 최단 경로 알고리즘(다익스트라, 플로이드-워셜 알고리즘)과 이전에 배웠던 스택과 재귀함수를 사용하는 DFS(깊이 우선 탐색), 큐를 활용하는 BFS(너비 우선 탐색)를 활용할 때 주로 이용된다. 그래서 '서로 다른 개체가 연결되어 있다' 는 이야기를 들으면 반사적으로 그래프 데이터를 활용한 알고리즘이라는 것을 떠올려야 한다.
그래프 데이터 즉, 그래프 자료구조 중에서 계층 구조인 트리 자료구조는 매우 자주 사용된다. 이전에 배웠던 heapq 라이브러리를 활용한 최소힙, 최대힙도 트리 자료 구조 중에 하나이다. 이전에 그래프 자료구조는 주로 2가지 형태로 주어진다고 했다. 바로 인접 행렬 형태와 인접 리스트 형태이다. 이 2가지의 장,단점에 대해 간단히 짚어보고 넘어가자.
메모리 측면에서 살펴보자. 딱 보아도 인접 행렬이 저장하는 정보가 많아 보인다. 즉, 노드 간에 연결되지 않은 정보도 0이라는 것으로 저장하므로 $O(V^2)$ 만큼의 메모리 공간이 필요하다. 하지만 인접 리스트 방식은 연결되어 있는 정보만을 저장하므로 연결된 간선의 개수 $E$ 만큼의 정보만 필요하므로 $O(E)$ 만큼의 메모리 공간이 필요하다.
이제 속도 측면에서 살펴보자. 만약 특정 노드에서 특정 노드까지 걸리는 비용을 확인하려고 한다면 인접 행렬 방식은 $O(1)$ 시간 복잡도 밖에 걸리지 않는다. 하지만 인접 리스트의 경우 최악의 경우 노드의 전체 개수인 $O(V)$만큼의 시간 복잡도가 걸린다.
그래서 그래프 데이터를 활용하는 문제에 직면했을 때, 메모리와 속도 측면에서 고려해서 적절한 데이터 형태를 정의하고 그에 맞는 그래프 알고리즘을 선택해야 한다.
1. 서로소 집합 자료구조란?
자, 이제 그러면 본격적으로 서로소 집합 자료구조에 대해 알아보자. 서로소 집합이란, 서로 공통 요소 즉, 교집합이 없는 서로 다른 집합을 의미한다. 예를 들어 {1, 2}, {2, 3}은 서로소 집합이 아니지만 {1, 2}, {4, 5}는 서로소 집합이다. 그래서 서로소 집합 자료구조란, 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 한다. 스택과 큐가 push, pop 연산과정이 있는 것처럼 서로소 집합 자료구조는 합집합 연산인 union 과 찾기 연산인 find 연산 2개로 이루어져 있다. 결국 이런 union, find 연산을 하게 되면 두 집합 간의 공통적인 요소가 있느냐 없느냐를 판단할 수 있는 연산이 된다. 아직 union? find?가 무엇인지 잘 감이 안온다. 좀 더 글을 읽어보면서 차근차근 이해해보자.
2. Union? Find?
서로소 집합 자료구조를 표시할 때는 기본적으로 트리 자료구조를 이용한다. 트리 자료구조는 계층을 갖고 있다. 즉, 노드들 간의 부모-자식 관계가 있음을 가정한다. 서로소 집합 정보(union 연산)가 주어졌을 때, 트리 자료구조를 활용해 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다.
- Union(합집합) 연산 정보 중 1개를 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
- 두 노드 A, B 각각의 루트노드 A', B'을 알아낸다.(이 때, Find 연산을 수행하는 셈)
- (보통은) A', B' 중 값이 작은 노드를 부모 노드라고 가정하고 연결시킨다. 예를 들어, A' < B' 이라면 B' -> A' 로 연결시킨다.(이 때, Union 연산을 수행하는 셈)
- 나머지 Union 연산 정보를 순차적으로 받으면서 1~3번 과정을 반복한다.
그림으로 도식화해보면 다음과 같다.
위와 같은 Union 연산 과정을 주어진 Union 연산 정보를 기준으로 수행한다. 그런데 가장 근본적인 궁금증이 있다. 필자는 해당 개념을 처음 접했을 때, 계속 고등학교때 배운 집합 개념만 머릿속에 맴돌아서, 대체 이 분야에서 서로소 집합 자료 구조가 무엇인지 이해가 안갔다. 그런 분들을 위해 아래의 그림과 같이 주어진 데이터가 있다고 가정하자.
위와 같이 Union 연산 정보가 주어 졌을 때, 방금 배운 Union 연산을 수행하면 위 자료구조와 같이 노드들 간의 부모-자식 관계가 연결된다. 이 때, 위 데이터에서 서로소 집합은 무엇이 될까? 바로 1과 5이다. 왜 1과 5일까? 우선 1, 2, 3, 4는 모두 1을 루트노드로 하는 집합들이다. 반면 5, 6은 5를 루트노드로 하는 집합들이다. 1, 2, 3, 4 와 5, 6 간의 연결된 Union 연산은 존재하지 않는다. 따라서 루트노드를 하나의 집합으로 하고 1과 5가 위 자료구조에서 서로소 집합이 된다.
3. 서로소 집합 알고리즘 동작 과정
그러면 이제 예제를 하나로 들어 서로소 집합 알고리즘이 어떻게 동작하는지 살펴보자.
3-1. 첫 번째 초기 단계
초기 단계에서 해야 할 가장 중요한 일은 노드의 개수만큼의 부모 테이블을 초기화 하는 것이다. 예를 들어, 노드의 개수가 $N$개 일 때, $N+1$ 길이의 1차원 리스트를 초기화한다. 이 때, 리스트의 원소값은 해당 인덱스값을 넣어준다. 즉, 처음에는 모든 원소가 자기 자신을 부모로 가지도록 설정한다. 초기단계로 다음과 같은 데이터가 주어졌다.
3-2. 두 번째 단계 - union 첫 번째 연산 수행
union 첫 번째 연산으로 (1, 4)가 들어왔다. 2번 목차에서 배운 Union 연산을 수행하며 다음과 같이 부모 테이블의 값을 업데이트 해준다.
위 처럼 Union 연산 정보에 의해 4번 노드의 부모 노드는 1번 노드라는 것을 알게 되었다. 따라서 위와 같이 부모테이블의 4번 인덱스 값을 4 -> 1로 업데이트 한다.
3-3. 세 번째 단계 - union 두 번째 연산 수행
이번에 주어진 Union 연산 정보에 의해 3번 노드의 부모 노드는 2번 노드이다. 따라서 위와 같이 부모 테이블의 3번 인덱스 값이 2번으로 업데이트 된다.
3-4. 네 번째 단계 - union 세 번째 연산 수행
여기서 헷갈리지 말아야 한다. 주어진 Union 연산 정보는 (2, 4) 이다. 즉 부모 테이블 상에서 4번 노드의 부모 노드(부모 테이블 값)는 1이다. 반면, 2번 노드의 부모 노드(부모 테이블 값)는 2이다. 따라서 4번 노드의 부모 노드 값이 1로 더 작으므로 2번 노드의 부모노드 값인 2는 1로 업데이트 해야 한다. 그래서 자료구조 그림 상으로는 2 -> 1번 노드로 가는 간선이 생겨난다.
3-5. 다섯 번째 단계 - union 네 번째 연산 수행
이번에 주어진 연산 정보에 의해 6번 노드의 부모 테이블 값은 5로 업데이트 된다. 그리고 모든 Union 연산을 수행했으니 알고리즘이 종료되고 다음과 같이 최종 부모 테이블이 완성된다.
위 부모 테이블을 해석하게 되면 6번 노드의 부모노드는 5번이고 5번의 부모노드는 5번으로 결국 하나의 서로소 집합으로 구성된다. 반면에 1,2,4번의 부모노드는 1이고 3번 노드의 부모노드는 2번 노드이지만 2번 노드의 부모노드는 재귀적으로 또 1번 노드이므로 결국 최종 루트 노드가 1번 노드로 또 하나의 서로소 집합으로 구성된다. 하지만 약간의 귀찮음(?)이 존재한다. 만약 1,2,4,5,6번의 루트노드가 무엇인지 조회하려 한다면 한 번에 루트노드로 조회되지만 3번 노드의 루트노드를 조회하게 되면 3 -> 2 -> 1로 한 번의 재귀과정을 추가로 거쳐야 한다. 이 불편함을 해소하기 위해서 아래에 '압축 경로'라는 테크닉을 사용하게 된다. 우선 이 테크닉은 잠시 옆으로 제쳐두고 지금까지 알아본 서로소 집합 알고리즘을 Python 소스 코드로 구현해보자.
4. 서로소 집합 알고리즘 Python으로 구현하기
import sys
v, e = map(int, input().split())
parent = [0] * (v+1)
for i in range(1, v+1):
parent[i] = i
# find 연산
def find_parent(parent, x):
# 부모노드와 자식노드 같지 않다면 = 부모노드가 따로 있는 의미니까!
if parent[x] != x:
return find_parent(parent, parent[x]) # 그 부모노드를 자식으로 하는 또 다른 부모노드를 재귀적으로 탐색
# 부모 노드 = 자식노드 -> 해당 노드 리턴
return x
def union_parent(parent, a, b):
# a, b 각 부모노드 탐색 - Find 연산
a = find_parent(parent, a)
b = find_parent(parent, b)
# 각 부모노드 비교 후 부모-자식 관계 형성 - Union 연산
if a < b:
parent[b] = a
else:
parent[a] = b
for _ in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
# 각 원소의 루트 노드 출력
print('# 각 원소의 루트 노드들: ', end='')
for i in range(1, v+1):
root = find_parent(parent, i)
print(root, end=' ')
print()
# 부모 테이블 출력(직계 부모노드를 의미)
print('# 각 원소의 직계 부모 노드들: ', end='')
for i in range(1, v+1):
print(parent[i], end=' ')5. 개선된 서로소 집합 알고리즘 Python 구현
아까 3-5번 목차 마지막 문단에서 기존 알고리즘의 문제점을 살짝 언급했었다. 부모 테이블에 루트노드가 들어가 있지 않은 값들은 최종 루트노드를 조회하기 위해 1번 이상 재귀적으로 추가로 호출해야 하는 상황이 발생한다. 결국 시간 복잡도가 늘어난다. 그래서 이를 개선하기 위해 압축 경로라는 테크닉을 이용하는데, 미리 부모 테이블에 부모 노드 값을 갱신해놓는 것이다. 하단의 find_parent 함수 생김새를 보면 차이점을 알 수 있다.
import sys
v, e = map(int, input().split())
parent = [0] * (v+1)
for i in range(1, v+1):
parent[i] = i
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
for _ in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
print('# 각 원소의 루트노드 출력:', end='')
for i in range(1, v+1):
root = find_parent(parent, i)
print(root, end=' ')
print()
print('# 위 find 연산 후 업데이트된 부모 테이블 출력:', end='')
for i in range(1, v+1):
print(parent[i], end=' ')6. 서로소 집합 알고리즘을 활용한 사이클 판별
서로소 집합은 무방향 그래프(간선에 방향이 없는 그래프) 내에서의 사이클을 판별할 때 사용이 가능하다. 참고로 유방향 그래프는 DFS를 활용해 사이클 판별이 가능하다고 하는데, 해당 책에서는 다루지 않지만 여기를 참고해서 알아두자.
그렇다면 서로소 집합 자료구조를 활용해서 무방향 그래프 내의 사이클을 어떻게 판별할 수 있을까? Union 연산 정보가 주어질 때 즉, 간선 정보가 주어질 때, 간선 하나하나를 확인하면서 Find 연산을 취해 각 노드의 부모노드를 찾는다. 그리고 찾아낸 2개의 부모 노드들이 같으면 사이클이 있다고 판별할 수 있고 만약 부모 노드들이 갖지 않다면 Union 연산을 취해서 부모-자식 간의 노드 관계를 형성한다.
이제 소스코드를 살펴보자. find, Union 연산하는 코드 지금까지 배운 것이랑 유사하며 부모 노드가 같은지 여부를 체크하면서 사이클이 존재하는지 판별하는 코드만 추가되었다.
import sys
v, e = map(int, input().split())
parent = [0] * (v+1)
for i in range(1, v+1):
parent[i] = i
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
cycle = False
for _ in range(e):
a, b = map(int, input().split())
if find_parent(parent, a) == find_parent(parent, b):
cycle = True
break
else:
union_parent(parent, a, b)
if cycle:
print('사이클이 존재합니다')
else:
print('사이클이 존재하지 않습니다')'Python > 알고리즘 개념' 카테고리의 다른 글
| [Python] 노드 간의 선후 관계를 고려하는 위상(Topology) 정렬 알고리즘 (0) | 2021.09.30 |
|---|---|
| [Python] 최소 신장 트리를 찾는 크루스칼(Kruskal) 알고리즘 (5) | 2021.09.29 |
| [Python] 모든 지점에서의 최단경로를 찾는 플로이드 워셜(Floyd-Warshall) 알고리즘 (0) | 2021.09.24 |
| [Python] 우선순위 큐를 활용한 개선된 다익스트라(Dijkstra) 알고리즘 (6) | 2021.09.23 |
| [Python] 최단경로를 위한 다익스트라(Dijkstra) 알고리즘 (0) | 2021.09.22 |
