안녕하세요, 여러분! 이번 블로그 포스트에서는 최소 신장 트리(Minimum Spanning Tree, MST)를 구하는 문제에 대해 알아보겠습니다. MST는 그래프의 모든 정점을 포함하면서, 간선의 합이 최소인 트리를 의미합니다. 이 문제는 네트워크 설계, 데이터 클러스터링, 그리고 그룹화를 포함한 다양한 분야에서 중요한 역할을 합니다.
문제 설명
다음과 같은 그래프가 주어졌을 때, 최소 신장 트리를 구하는 문제를 해결해 보겠습니다.
입력:
5 6
1 2 1
1 3 3
2 3 2
2 4 4
3 4 5
4 5 6
여기서 첫 줄의 ‘5 6’은 각각 정점의 개수와 간선의 개수를 의미합니다. 이어지는 줄에서는 각 간선과 그 가중치가 주어집니다. 예를 들어 ‘1 2 1’은 정점 1과 정점 2를 연결하는 간선의 가중치가 1이라는 의미입니다.
출력 형식
최소 신장 트리에 포함된 간선의 목록과 해당 간선의 가중치의 합을 출력해야 합니다.
문제 풀이 접근법
최소 신장 트리를 구하는 방법에는 여러 가지가 있지만, 여기서는 대표적으로 프림(Prim’s) 알고리즘과 크루스칼(Kruskal’s) 알고리즘을 사용해 보겠습니다. 두 가지 방법 모두 효율적이며, 상황에 따라 다르게 적용할 수 있습니다.
프림 알고리즘
프림 알고리즘은 특정 정점에서 시작하여 가장 작은 가중치를 가진 간선을 선택함으로써 점차적으로 트리를 확장해 나가는 방식입니다. 전체 과정은 다음과 같습니다:
- 시작 정점을 선택하고, 해당 정점을 방문한 것으로 표시합니다.
- 현재 트리와 연결된 간선 중 가중치가 가장 낮은 간선을 선택합니다.
- 새로운 정점을 방문하고 트리에 추가합니다.
- 1~3단계를 모든 정점을 방문할 때까지 반복합니다.
C# 코드 구현
아래는 프림 알고리즘을 C#으로 구현한 예제입니다:
using System;
using System.Collections.Generic;
class Graph
{
public int Vertices { get; set; }
public List> Edges { get; set; }
public Graph(int vertices)
{
Vertices = vertices;
Edges = new List>();
}
public void AddEdge(int u, int v, int weight)
{
Edges.Add(Tuple.Create(u, v, weight));
}
public void PrimsMST()
{
int[] parent = new int[Vertices];
int[] key = new int[Vertices];
bool[] mstSet = new bool[Vertices];
for (int i = 0; i < Vertices; i++)
{
key[i] = Int32.MaxValue;
mstSet[i] = false;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < Vertices - 1; count++)
{
int u = MinKey(key, mstSet);
mstSet[u] = true;
foreach (var edge in Edges)
{
int v = edge.Item2;
int weight = edge.Item3;
if (edge.Item1 == u && !mstSet[v] && weight < key[v])
{
parent[v] = u;
key[v] = weight;
}
}
}
PrintResult(parent);
}
private int MinKey(int[] key, bool[] mstSet)
{
int min = Int32.MaxValue, minIndex = -1;
for (int v = 0; v < Vertices; v++)
{
if (mstSet[v] == false && key[v] < min)
{
min = key[v];
minIndex = v;
}
}
return minIndex;
}
private void PrintResult(int[] parent)
{
Console.WriteLine("간선 \t 가중치");
int totalWeight = 0;
for (int i = 1; i < Vertices; i++)
{
Console.WriteLine(parent[i] + " - " + i + "\t " + Edges[i].Item3);
totalWeight += Edges[i].Item3;
}
Console.WriteLine("최소 신장 트리의 총 가중치: " + totalWeight);
}
}
class Program
{
static void Main(string[] args)
{
int vertices = 5;
Graph g = new Graph(vertices);
g.AddEdge(1, 2, 1);
g.AddEdge(1, 3, 3);
g.AddEdge(2, 3, 2);
g.AddEdge(2, 4, 4);
g.AddEdge(3, 4, 5);
g.AddEdge(4, 5, 6);
g.PrimsMST();
}
}
위 코드에서 Graph 클래스는 그래프의 정점과 간선을 저장하며, AddEdge 메서드를 사용해 간선을 추가합니다. PrimsMST 메서드는 프림 알고리즘의 로직을 구현하고 있습니다. 가중치가 가장 작은 간선을 반복적으로 선택하여 최소 신장 트리를 완성합니다.
크루스칼 알고리즘
크루스칼 알고리즘은 간선을 기준으로 가중치를 오름차순으로 정렬한 후, 사이클이 생기지 않도록 간선을 선택하는 방식입니다. 이 알고리즘의 과정은 다음과 같습니다:
- 그래프의 모든 간선을 가중치에 따라 정렬합니다.
- 각 간선을 하나씩 선택하며, 선택한 간선이 현재의 트리에 포함되어도 사이클이 생기지 않는 경우 추가합니다.
- 위 과정을 최소 신장 트리가 완성될 때까지 반복합니다.
C# 코드 구현
아래는 크루스칼 알고리즘을 C#으로 구현한 예제입니다:
using System;
using System.Collections.Generic;
class Edge : IComparable
{
public int Source { get; set; }
public int Destination { get; set; }
public int Weight { get; set; }
public int CompareTo(Edge other)
{
return this.Weight.CompareTo(other.Weight);
}
}
class Graph
{
public int Vertices { get; set; }
public List Edges { get; set; }
public Graph(int vertices)
{
Vertices = vertices;
Edges = new List();
}
public void AddEdge(int source, int destination, int weight)
{
Edges.Add(new Edge { Source = source, Destination = destination, Weight = weight });
}
public void KruskalsMST()
{
Edges.Sort();
int[] parent = new int[Vertices];
for (int i = 0; i < Vertices; i++)
parent[i] = -1;
int totalWeight = 0;
foreach (var edge in Edges)
{
int x = FindParent(parent, edge.Source);
int y = FindParent(parent, edge.Destination);
if (x != y)
{
totalWeight += edge.Weight;
Console.WriteLine("간선: " + edge.Source + " - " + edge.Destination + " 가중치: " + edge.Weight);
Union(parent, x, y);
}
}
Console.WriteLine("최소 신장 트리의 총 가중치: " + totalWeight);
}
private int FindParent(int[] parent, int i)
{
if (parent[i] == -1)
return i;
return FindParent(parent, parent[i]);
}
private void Union(int[] parent, int x, int y)
{
parent[x] = y;
}
}
class Program
{
static void Main(string[] args)
{
int vertices = 5;
Graph g = new Graph(vertices);
g.AddEdge(1, 2, 1);
g.AddEdge(1, 3, 3);
g.AddEdge(2, 3, 2);
g.AddEdge(2, 4, 4);
g.AddEdge(3, 4, 5);
g.AddEdge(4, 5, 6);
g.KruskalsMST();
}
}
위 코드에서 Graph 클래스는 크루스칼 알고리즘을 위한 구조로, 간선을 관리하며 MST를 계산하는 KruskalsMST 메서드를 포함합니다. 간선을 가중치에 따라 정렬하고, 트리에 추가할 수 있는지 확인한 후 추가합니다.
결론
이번 포스트에서 최소 신장 트리를 구하는 두 가지 알고리즘, 즉 프림 알고리즘과 크루스칼 알고리즘을 살펴보았습니다. 두 알고리즘 모두 효율적이며 특정 경우에 따라 상대적인 이점을 가집니다. 실제 코딩 테스트에서는 문제의 조건과 그래프의 형태에 따라 적절한 알고리즘을 선택하는 것이 중요합니다. 이러한 알고리즘은 실무에서도 많이 사용되며, 알고리즘 문제 풀이 능력을 향상하는 데 좋은 연습이 됩니다.
이 과정을 통해 여러분이 최소 신장 트리에 대한 이해를 높이고, C# 코딩 테스트에 대비하는 데 도움이 되었길 바랍니다. 다음 시간에는 다른 알고리즘 주제로 찾아뵙겠습니다. 감사합니다!