코딩 테스트에서 자주 등장하는 문제 중 하나는 ‘최소 비용 구하기’ 문제입니다.
이 문제는 특정 조건을 만족시키면서 비용을 최소화해야 하는 상황에서,
다양한 알고리즘을 활용하여 효율적으로 해결할 수 있습니다.
이번 글에서는 C#을 이용해 최소 비용 구하기 문제를 해결하는 방법을 자세히 살펴보겠습니다.
문제 설명
주어진 그래프에서 각 간선은 특정 비용을 가지고 있습니다.
시작 정점에서 다른 모든 정점으로 가는 최소 비용 경로를 찾는 문제가 주어졌을 때,
우리는 이를 효율적으로 해결해야 합니다.
문제 정의
정점의 개수는 N, 간선의 개수는 M이라고 가정할 때,
다음과 같은 조건을 만족하는 그래프가 주어진다고 합시다.
- N (1 <= N <= 1000): 정점의 개수
- M (1 <= M <= 10000): 간선의 개수
- 비용은 1 이상 10000 이하의 정수
입력: 시작 정점과 각 정점 간의 비용 정보가 주어진다.
출력: 시작 정점에서 다른 모든 정점으로 가는 최소 비용 경로의 배열을 출력한다.
예시
입력
5 7
1 2 2
1 3 3
2 3 1
2 4 5
3 4 1
3 5 5
4 5 2
1
출력
0 2 3 7 5
위의 예시에서 정점 1에서 출발했을 때,
정점 2까지는 2, 정점 3까지는 3, 정점 4까지는 7, 정점 5까지는 5의 비용이 필요합니다.
각 비용이 최소가 되도록 경로를 설정해야 합니다.
알고리즘 설명
문제를 해결하기 위해 Dijkstra 알고리즘을 활용할 것입니다.
Dijkstra 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘으로,
다음과 같은 절차로 진행됩니다:
- 시작 정점을 설정하고, 이 정점의 거리 값을 0으로 설정합니다.
- 모든 다른 정점의 거리 값을 무한대로 초기화합니다.
- 가장 비용이 적게 드는 정점을 선택하여 주변 정점으로의 거리 값을 갱신합니다.
- 모든 정점에 대해 위 과정을 반복합니다. 최종적으로 각 정점에 대한 최소 비용이 계산됩니다.
C# 구현
이제 Dijkstra 알고리즘을 C#으로 구현해 보겠습니다.
먼저 필요한 라이브러리를 참조하고, 그래프를 표현하기 위해 인접 리스트를 사용하겠습니다.
using System;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
int n = 5; // 정점 개수
int m = 7; // 간선 개수
List> edges = new List>()
{
Tuple.Create(1, 2, 2),
Tuple.Create(1, 3, 3),
Tuple.Create(2, 3, 1),
Tuple.Create(2, 4, 5),
Tuple.Create(3, 4, 1),
Tuple.Create(3, 5, 5),
Tuple.Create(4, 5, 2)
};
int start = 1; // 시작 정점
var result = Dijkstra(n, m, edges, start);
Console.WriteLine(string.Join(" ", result));
}
static int[] Dijkstra(int n, int m, List> edges, int start)
{
// 그래프 초기화
List>> graph = new List>>(n + 1);
for (int i = 0; i <= n; i++)
{
graph.Add(new List>());
}
// 간선 추가
foreach (var edge in edges)
{
graph[edge.Item1].Add(Tuple.Create(edge.Item2, edge.Item3));
}
// 거리 초기화
int[] distance = new int[n + 1];
bool[] visited = new bool[n + 1];
for (int i = 1; i <= n; i++) distance[i] = int.MaxValue;
// 시작 정점
distance[start] = 0;
PriorityQueue> pq = new PriorityQueue>();
pq.Enqueue(Tuple.Create(0, start));
while (pq.Count > 0)
{
var current = pq.Dequeue();
int dist = current.Item1;
int node = current.Item2;
if (visited[node]) continue;
visited[node] = true;
foreach (var neighbor in graph[node])
{
int newDist = dist + neighbor.Item2;
if (newDist < distance[neighbor.Item1])
{
distance[neighbor.Item1] = newDist;
pq.Enqueue(Tuple.Create(newDist, neighbor.Item1));
}
}
}
return distance[1..]; // 시작 정점을 제외한 거리 반환
}
}
// 우선순위 큐 클래스 정의
public class PriorityQueue
{
List elements = new List();
public int Count => elements.Count;
public void Enqueue(T item)
{
elements.Add(item);
var index = elements.Count - 1;
while (index > 0)
{
var parentIndex = (index - 1) / 2;
if (Compare(elements[index], elements[parentIndex]) >= 0) break;
Swap(index, parentIndex);
index = parentIndex;
}
}
public T Dequeue()
{
var lastIndex = elements.Count - 1;
var firstElement = elements[0];
elements[0] = elements[lastIndex];
elements.RemoveAt(lastIndex);
--lastIndex;
int index = 0;
while (true)
{
var leftChildIndex = index * 2 + 1;
var rightChildIndex = index * 2 + 2;
int smallestChildIndex;
if (leftChildIndex > lastIndex) break;
if (rightChildIndex > lastIndex) smallestChildIndex = leftChildIndex;
else smallestChildIndex = Compare(elements[leftChildIndex], elements[rightChildIndex]) < 0 ? leftChildIndex : rightChildIndex;
if (Compare(elements[index], elements[smallestChildIndex]) <= 0) break;
Swap(index, smallestChildIndex);
index = smallestChildIndex;
}
return firstElement;
}
void Swap(int indexA, int indexB)
{
var temp = elements[indexA];
elements[indexA] = elements[indexB];
elements[indexB] = temp;
}
int Compare(T a, T b)
{
// 사용자 정의 비교 로직 여기에 구현 필요
// 예를 들어, Tuple의 경우
return a.Item1.CompareTo(b.Item1);
}
}
알고리즘 분석
위의 알고리즘을 사용하면 시간 복잡도는 O((N + M) log N)입니다.
여기서 N은 정점의 수, M은 간선의 수입니다.
Dijkstra 알고리즘은 일반적으로 비효율적이지 않으며,
많은 경우에 최소 비용을 구하는 데 효과적입니다.
단, 모든 간선의 가중치가 음수가 아니어야 한다는 점을 유의해야 합니다.
결론
이번 강좌에서는 C#을 통해 최소 비용 구하기 문제를 해결하기 위한 Dijkstra 알고리즘을
살펴보았습니다. 문제를 정의하고, 알고리즘을 설명한 후
실제 코드를 구현하는 과정을 차근차근 진행했습니다.
코딩 테스트에서 이러한 문제들이 자주 출제되므로, 충분히 연습하고 이해하는 것이 중요합니다.
이번 글이 코딩 테스트 준비에 도움이 되길 바랍니다.