이코테 강의를 통해서 공부했습니다!
크루스칼 알고리즘
신장 트리
- 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 신장 트리라 한다.
크루스칼 알고리즘
- 크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘이다.
- 그리디 알고리즘의 한 종류이다. → 주어진 상황에서 최선의 선택(최소 비용 간선 선택)을 한다!
- 크루스칼 알고리즘의 동작 과정
- 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
a. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
b. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음
- 모든 간선에 대하여 2번의 과정을 반복한다.
크루스칼 알고리즘 구현
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
num_node, num_edge = map(int, input().split())
parent_table = [0] * (num_node + 1)
edges = []
result = 0
for i in range(1, num_node + 1):
parent_table[i] = i
for _ in range(num_edge):
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_table, a) != find_parent(parent_table, b):
union_parent(parent_table, a, b)
result += cost
print(result)
크루스칼 알고리즘 성능 분석
- 크루스칼 알고리즘에서 가장 많은 시간을 요구하는 곳은 간선 정렬 부분
- 표준 라이브러리의 시간 복잡도가 O(nlogn)이므로 E개의 간선을 정렬하는 연산의 시간 복잡도는
O(ElogE)
가 된다.
크루스칼 알고리즘 백준 문제
1647번 : 도시 분할 계획
1647번: 도시 분할 계획
솔루션 아이디어
- 모든 집 사이에 경로가 존재 & 유지비의 합을 최소로
→ 최소 비용 신장 트리, 크루스칼 알고리즘 이용
- 두 개의 마을로 분할한다
→ 신장 트리를 두 개 만들겠다고 접근하면 머리가 아프다.
→ 한 개의 신장 트리를 완성하고, 거기서 하나의 간선을 제거하면 두 개의 신장트리가 생긴다는 것을 이용한다!
→ 이때, 비용을 최소로 하려면 가장 비용이 큰 간선을 제거하면 된다.
솔루션 코드
import sys
input = sys.stdin.readline
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
num_node, num_edge = map(int, input().split())
parent_table = [0] * (num_node+ 1)
edges = []
result_edges = []
for i in range(1, num_node + 1):
parent_table[i] = i
for _ in range(num_edge):
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_table, a) != find_parent(parent_table, b):
union_parent(parent_table, a, b)
result_edges.append(cost)
print(sum(result_edges) - max(result_edges))