프로그래밍에서 그래프를 다루는 문제들은 많이 나오는데요, 그 중에서도 특히 최소비용신장트리를 구하는 문제는 자주 출제되는 유형입니다. 최소비용신장트리란, 그래프의 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리를 말합니다. 예를 들어, 도시들을 연결하는 도로를 건설할 때, 최소한의 비용으로 모든 도시를 연결하려면 어떻게 해야 할까요? 이런 문제를 해결할 수 있는 알고리즘이 바로 최소비용신장트리알고리즘입니다. 이 알고리즘은 크게 두 가지 방법으로 구현할 수 있는데, 바로 크루스칼 알고리즘과 프림 알고리즘입니다. 이번 포스팅에서는 이 두 가지 알고리즘의 원리와 구현 방법에 대해 자세히 알아보겠습니다.
크루스칼 알고리즘은 간단히 말하면, 가중치가 작은 간선부터 차례대로 선택하면서 최소비용신장트리를 만드는 방법입니다. 다음과 같은 순서로 진행됩니다.
- 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬합니다.
- 정렬된 간선 리스트에서 순서대로 하나씩 선택합니다.
- 선택한 간선이 사이클을 발생시키지 않으면, 최소비용신장트리에 포함시킵니다.
- 모든 정점이 연결될 때까지 2~3번 과정을 반복합니다.
사이클을 발생시키지 않는지 확인하기 위해서는 유니온-파인드(Union-Find)라는 자료구조를 사용합니다. 유니온-파인드란, 각 정점들의 부모 정점을 저장하고 관리하는 자료구조로, 두 정점이 같은 부모를 가지면 사이클이 발생한 것으로 판단할 수 있습니다. 유니온-파인드의 구현 방법은 다음과 같습니다.
- 초기화: 모든 정점의 부모를 자기 자신으로 설정합니다.
- 파인드(Find): 재귀적으로 부모 정점을 찾아 반환합니다. 경로 압축(Path Compression) 기법을 사용하여 부모 정점을 찾으면서 중간에 거치는 정점들의 부모를 최상위 부모로 바꿔줍니다. 이렇게 하면 다음에 같은 정점을 찾을 때 더 빠르게 찾을 수 있습니다.
- 유니온(Union): 두 정점의 부모를 파인드 함수로 찾아서, 두 부모가 다르면 한쪽의 부모를 다른 쪽의 부모로 설정합니다. 이렇게 하면 두 정점이 같은 집합에 속하게 됩니다.
크루스칼 알고리즘의 시간 복잡도는 O(ElogE)입니다. E는 간선의 개수이고, 간선을 정렬하는데 O(ElogE)의 시간이 걸리기 때문입니다. 유니온-파인드 연산은 상수 시간에 수행할 수 있습니다.
크루스칼 알고리즘의 예시 코드는 다음과 같습니다.
[python]
# 파이썬으로 구현한 크루스칼 알고리즘
# 그래프의 정점과 간선의 개수
V, E = map(int, input().split())
# 간선 리스트
edges = []
# 최소비용신장트리의 가중치 합
answer = 0
# 부모 정점을 저장하는 리스트
parent = [i for i in range(V+1)]
# 간선 정보 입력받기
for _ in range(E):
u, v, w = map(int, input().split())
edges.append((w, u, v))
# 간선을 가중치에 따라 오름차순으로 정렬
edges.sort()
# 파인드 함수: 재귀적으로 부모 정점을 찾고, 경로 압축
def find(x):
if parent[x] == x:
return x
else:
parent[x] = find(parent[x])
return parent[x]
# 유니온 함수: 두 정점의 부모를 비교하고, 다르면 한쪽의 부모를 다른 쪽으로 설정
def union(x, y):
x = find(x)
y = find(y)
if x != y:
parent[y] = x
# 크루스칼 알고리즘
for edge in edges:
w, u, v = edge
# 사이클이 발생하지 않으면, 최소비용신장트리에 포함시키고 가중치를 더함
if find(u) != find(v):
union(u, v)
answer += w
# 결과 출력
print(answer)
프림 알고리즘
프림 알고리즘은 간단히 말하면, 임의의 정점부터 시작해서 연결된 간선 중에서 가중치가 작은 것부터 선택하면서 최소비용신장트리를 만드는 방법입니다. 다음과 같은 순서로 진행됩니다.
- 임의의 정점을 선택하고, 방문한 정점 집합에 추가합니다.
- 선택한 정점과 연결된 간선들 중에서 가중치가 작은 순서대로 우선순위 큐에 삽입합니다.
- 우선순위 큐에서 하나씩 꺼내면서, 꺼낸 간선이 연결하는 정점이 방문한 정점 집합에 속하지 않으면, 최소비용신장트리에 포함시키고 방문한 정점 집합에 추가합니다.
- 모든 정점이 연결될 때까지 2~3번 과정을 반복합니다.
프림 알고리즘의 시간 복잡도는 O(ElogV)입니다. V는 정점의 개수이고, 우선순위 큐에 간선을 삽입하고 꺼내는데 O(ElogV)의 시간이 걸리기 때문입니다. 프림 알고리즘은 간선의 개수가 많고 정점의 개수가 적은 밀집 그래프(Dense Graph)에 적합합니다.
프림 알고리즘의 예시 코드는 다음과 같습니다.
[python]
# 파이썬으로 구현한 프림 알고리즘
import heapq # 우선순위 큐를 사용하기 위한 모듈
# 그래프의 정점과 간선의 개수
V, E = map(int, input().split())
# 인접 리스트
adj = [[] for _ in range(V+1)]
# 최소비용신장트리의 가중치 합
answer = 0
# 방문한 정점을 저장하는 집합
visited = set()
# 간선 정보 입력받기
for _ in range(E):
u, v, w = map(int, input().split())
adj[u].append((w, v))
adj[v].append((w, u))
# 프림 알고리즘
def prim(start):
global answer
# 우선순위 큐 생성
pq = []
# 시작 정점을 방문한 집합에 추가하고, 인접한 간선들을 우선순위 큐에 삽입
visited.add(start)
for edge in adj[start]:
heapq.heappush(pq, edge)
# 우선순위 큐가 빌 때까지 반복
while pq:
# 가중치가 가장 작은 간선을 꺼냄
w, v = heapq.heappop(pq)
# 꺼낸 간선이 연결하는 정점이 방문한 집합에 속하지 않으면, 최소비용신장트리에 포함시키고 가중치를 더함
if v not in visited:
visited.add(v)
answer += w
# 새로 방문한 정점과 연결된 간선들을 우선순위 큐에 삽입
for edge in adj[v]:
heapq.heappush(pq, edge)
# 임의의 정점부터 시작
prim(1)
# 결과 출력
print(answer)
이번 포스팅에서는 최소비용신장트리알고리즘에 대해 알아보았습니다. 크루스칼 알고리즘과 프림 알고리즘은 각각 다른 방식으로 최소비용신장트리를 구하는데, 상황에 따라 적절하게 사용할 수 있어야 합니다. 이 알고리즘들을 잘 이해하고 응용하면, 그래프 문제를 효율적으로 해결할 수 있을 것입니다. 다음 포스팅에서는 다익스트라 알고리즘에 대해 알아보겠습니다. 읽어주셔서 감사합니다!
'알고리즘 > 알고리즘 이론 및 응용' 카테고리의 다른 글
| 다이나믹 프로그래밍이란? 작은 문제로 나누고 메모이제이션하는 기법 (0) | 2023.09.05 |
|---|---|
| 알고리즘 이론 및 응용 (0) | 2023.06.12 |