목표 : 이것이 코딩테스트이다 with python 에서 그래프 이론을 공부해보자.
"서로 다른 개체(혹은 객체)가 연결되어 있다" => 그래프 알고리즘 떠올리자!
그래프 자료구조에서 트리(Tree) 자료구조는 꼭 기억하자!
트리의 특징
- 방향 그래프
- 비순환
- 루트 노드가 존재
- 부모와 자식 관계
- 계층 모델
그래프의 특징
- 방향 혹은 무방향 그래프
- 순환 및 비순환
- 루트 노드가 없음
- 부모와 자식 관계 없음
- 네트워크 모델
union(합집합) : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
find(찾기) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
서로소 집합 알고리즘
- union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
- A와 B의 루트 노두 A', B'를 각각 찾는다.
- A'를 B'의 부모 노드로 설정한다.(B'가 A'를 가리키도록 한다)
- 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.
Code
# 기본적인 서로소 집합 알고리즘 소스코드
# 특정 원소가 속한 집합을 찾기
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=' ')
결과
find(찾기) 함수의 최적화 => 경로 압축 기법 : find 함수를 재귀적으로 호출한 뒤에 부모 테이블을 갱신하는 방식
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
다음과 같이 수정하였더니 부모 테이블이 갱신된 결과를 얻을 수 있었다.
결과
서로소 집합을 활용한 사이클 판별 알고리즘
- 각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
- 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.
- 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것이다.
- 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.
Code
# 특정 원소가 속한 집합을 찾기
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
v, e = map(int, input().split())
parent = [0] * (v + 1)
for i in range(1, v + 1):
parent[i] = 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
else:
union_parent(parent, a, b)
if cycle:
print("사이클이 발생했습니다.")
else:
print("사이클이 발생하지 않았습니다.")
결과
하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건 => 트리의 조건
- 대표적인 최소 신장 트리 알고리즘 으로 가장 적은 비용으로 모든 노드를 연결할 수 있다.
- 그리디 알고리즘으로 분류된다.
- 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
- 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
- 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
- 모든 간선에 대하여 2번의 과정을 반복한다.
최소 신장 트리는 일종의 트리자료구조이므로 간선의 개수 = 노드의 개수 - 1 과 같다는 특징이 있다.
Code
# 크루스칼 알고리즘 소스코드
# 특정 원소가 속한 집합을 찾기
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)
# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
parent[i] = i
# 모든 간선에 대한 정보를 입력받기
for _ in range(e):
a, b, cost = map(int, input().split())
# 비용순으로 정렬하기 위해 튜플의 첫 번째 원소를 비용으로 설정
edges.append((cost, a, b))
# 간선을 비용순으로 정렬
edges.sort()
for edge in edges:
cost, a, b = edge
# 사이클이 발생하지 않는 경우에만 집합에 포함
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(result)
결과