1. 서론
컴퓨터 과학 및 프로그래밍 분야에서 알고리즘은 문제를 해결하기 위한 필수적인 도구입니다. 특히, 코딩 테스트는 개발자에게 매우 중요한 요소 중 하나로, 알고리즘 및 자료구조에 대한 이해가 요구됩니다. 이번 강좌에서는 최소 신장 트리(Minimum Spanning Tree, MST)의 개념과 이를 활용한 알고리즘 문제를 다뤄보겠습니다.
2. 최소 신장 트리란?
최소 신장 트리는 연결 그래프의 부분 그래프 중에서 모든 정점을 포함하고 사이클을 포함하지 않으면서 모든 간선의 가중치의 합이 최소인 트리입니다. 그래프의 정점과 간선, 가중치에 대해 이해하는 것이 중요합니다. 최소 신장 트리는 주로 클러스터링, 네트워크 설계, 거리가 최소한으로 유지되는 다양한 문제 해결 등에서 활용됩니다.
2.1 MST의 성질
- 모든 정점이 포함되어야 합니다.
- 사이클이 존재하지 않습니다.
- 가중치의 합이 최소입니다.
3. 최소 신장 트리를 찾는 알고리즘
최소 신장 트리를 찾는 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있습니다. 두 알고리즘은 각각 다른 접근 방식을 사용하지만, 최종적으로는 동일한 결과를 생성합니다.
3.1 크루스칼 알고리즘
크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택하면서 신장 트리를 만들어나가는 방식입니다. 이 알고리즘은 주어진 간선을 가중치의 오름차순으로 정렬한 후, 순서대로 간선을 선택해 나갑니다. 이 때, 사이클이 발생하지 않도록 주의해야 합니다.
3.2 프림 알고리즘
프림 알고리즘은 하나의 정점에서 시작하여 그 정점에 연결된 가장 가중치가 적은 간선을 선택하여 진행합니다. 이 방식은 정점의 개수가 많을 때 더욱 효율적입니다.
4. 문제 설명
이제 실제 문제를 해결하는 과정을 살펴보겠습니다. 다음은 최소 신장 트리를 구하는 문제입니다.
문제: 최소 신장 트리 구하기
입력:
- 정점의 수
V(1 ≤ V ≤ 1000) - 간선의 수
E(1 ≤ E ≤ 10000) - 각 간선은
u, v, w형태로 주어지며, u와 v는 정점의 번호, w는 두 정점을 연결하는 간선의 가중치입니다.
출력: 최소 신장 트리를 구성하는 간선의 가중치 합을 출력합니다.
5. 문제 풀이
문제를 해결하기 위해 크루스칼 알고리즘을 사용하겠습니다. 이 알고리즘은 다음과 같은 단계로 진행됩니다.
5.1 간선 정렬
입력받은 모든 간선을 가중치의 오름차순으로 정렬합니다. 정렬된 간선은 최소 신장 트리를 구성할 때 선택되는 기준이 됩니다.
5.2 사이클 확인
정렬된 간선을 하나씩 선택하여 두 정점이 서로 다른 집합에 속하는지 확인합니다. 이를 위해 유니온-파인드(Union-Find) 자료구조를 사용합니다.
5.3 간선 추가 및 가중치 합산
사이클이 발생하지 않으면 해당 간선을 최소 신장 트리의 간선 목록에 추가하고, 가중치를 합산합니다. 이 과정을 반복하여 모든 간선을 처리합니다.
5.4 C# 구현
이제 위의 과정을 C# 코드로 구현해보겠습니다.
using System;
using System.Collections.Generic;
using System.Linq;
class Edge
{
public int U { get; set; }
public int V { get; set; }
public int Weight { get; set; }
}
class UnionFind
{
private int[] parent;
public UnionFind(int size)
{
parent = new int[size];
for (int i = 0; i < size; i++)
parent[i] = i;
}
public int Find(int u)
{
if (parent[u] != u)
parent[u] = Find(parent[u]);
return parent[u];
}
public void Union(int u, int v)
{
int rootU = Find(u);
int rootV = Find(v);
if (rootU != rootV)
parent[rootU] = rootV;
}
}
class Program
{
static void Main()
{
int V = int.Parse(Console.ReadLine());
int E = int.Parse(Console.ReadLine());
List edges = new List();
for (int i = 0; i < E; i++)
{
string[] input = Console.ReadLine().Split();
edges.Add(new Edge { U = int.Parse(input[0]), V = int.Parse(input[1]), Weight = int.Parse(input[2]) });
}
edges = edges.OrderBy(e => e.Weight).ToList();
UnionFind uf = new UnionFind(V + 1);
int totalWeight = 0;
foreach (var edge in edges)
{
if (uf.Find(edge.U) != uf.Find(edge.V))
{
uf.Union(edge.U, edge.V);
totalWeight += edge.Weight;
}
}
Console.WriteLine(totalWeight);
}
} 6. 시간 복잡도
크루스칼 알고리즘의 전체 시간 복잡도는 아래와 같습니다.
- 간선 정렬:
O(E log E) - 유니온-파인드:
O(E α(V))(α는 아커만 함수의 역함수)
따라서 전체적으로 O(E log E)의 시간 복잡도를 가집니다. 이로 인해 간선의 수가 많을 경우에도 상대적으로 효율적인 성능을 나타냅니다.
7. 결론
이번 강좌에서는 최소 신장 트리에 대해 알아보았습니다. 크루스칼 알고리즘을 사용하여 최소 신장 트리를 구하는 방법을 배우고, 그 과정을 C# 코드를 통해 실습하였습니다. 최소 신장 트리는 다양한 그래프 문제에서 응용될 수 있으며, 알고리즘적 사고를 기르는 데 중요한 역할을 합니다. 다음 강좌에서는 더 다양한 알고리즘 및 자료구조를 탐구해보겠습니다.