이전 DFS/BFS 와 최단경로 에서 다룬 내용은 모두 그래프 알고리즘의 한 유형으로 볼 수 있다.
그래프
- 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조
- 문제를 접했을 때 '서로 다른 개체가 연결되어 있다'는 말을 들으면 가장 먼저 그래프 알고리즘을 떠올려야 한다.
- 구현 방법
- 인접 행렬 : 2차원 배열을 사용하는 방식
- 인접 리스트 : 리스트를 사용하는 방식
- 노드의 개수가 V, 간선의 개수가 E인 그래프인 경우
인접행렬 : 공간 복잡도O(v^2), 시간 복잡도O(1)
인접리스트 : 공간 복잡도O(E), 시간 복잡도O(V)
트리
- 부모에서 자식으로 내려오는 계층적인 모델
| 그래프 | 트리 | |
|---|---|---|
| 방향성 | 방향 그래프 혹은 무방향 그래프 | 방향 그래프 |
| 순환성 | 순환 및 비순환 | 비순환 |
| 루트 노드 존재 여부 | 루트 노드가 없음 | 있음 |
| 노드간 관계성 | 부모와 자식 관계 없음 | 부모와 자식 관계 |
| 모델의 종류 | 네트워크 모델 | 계층모델 |
서로소 집합
서로소 집합 : 공통 원소가 없는 두 집합
서로소 집합 자료구조: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
- 서로소 집합 자료구조는 union과 find 두 개의 연산으로 조작할 수 있다.
- union(합집합) : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
- find(찾기) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
- 서로소 집합 자료구조는 트리 자료구조를 이용하여 집합을 표현한다.
- 서로소 집합 정보가 주어졌을 때 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다.
1 union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
1. A와 B의 루트 노드 A', B'를 각각 찾는다.
2. A'를 B'의 부모 노드로 설정한다(B'가 A'를 가리키도록 한다.)
2 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.
#특정 원소가 속한 집합을 찾기
def find_parents(number):
#루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parents[number] != number:
return find_parents(parents[number])
return number
#두 원소가 속한 집합을 합치기
def union(a, b):
a = find_parents(a)
b = find_parents(b)
if a < b:
parents[b] = a
else:
parents[a] = b
#노드의 개수와 간선의 개수 입력받기
n, k = map(int, input().split())
#부모 테이블 생성
parents = [i for i in range(n + 1)] #부모 테이블 초기화
for i in range(k):
one, two = map(int, input().split())
union(one, two)
print("각 원소가 속한 집합 : ", end="")
for i in range(1, n+1):
print(find_parents(i), end=" ")
print()
print("부모 테이블 : ", end="")
for i in range(1, n+1):
print(parents[i], end=" ")
화이링~!