안녕하세요, 여러분! 이번 포스팅에서는 C#을 활용한 코딩테스트 문제를 다뤄보겠습니다. 주제는 “세일즈맨의 고민”입니다. 이 문제는 알고리즘에서 많이 다루는 경로 최적화 문제로, 최적 경로 탐색 및 성능 개선의 중요한 개념을 이해하는 데 유용합니다.
문제 설명
한 세일즈맨이 N개의 도시를 방문해야 합니다. 각 도시 간의 거리 정보가 주어지며, 세일즈맨은 모든 도시를 한 번씩 방문한 후 다시 시작 도시로 돌아와야 합니다. 세일즈맨은 최소 거리를 통해 모든 도시를 방문하는 경로를 찾아야 합니다. 이 문제는 그러므로 주어진 도시들과 거리 정보를 기반으로 최적의 경로를 찾는 ‘외판원 문제(Travelling Salesman Problem, TSP)’에 해당합니다.
문제 정의
주어진 입력:
1. 도시는 N (1 <= N <= 10, 도시 수)
2. 각 도시 간의 거리 정보가 주어지는 2차원 배열 dist[n][n] (0 <= dist[i][j] <= 10^4)
출력:
1. 모든 도시를 통과하는 최소 거리 값
입력 예시
N = 4
dist = [[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]]
이 예제의 설명:
이 배열에서 dist[i][j]는 도시 i에서 도시 j까지의 거리를 의미합니다. 세일즈맨은 모든 도시를 방문하고 최소의 거리를 통해 돌아와야 합니다. 예를 들어, 시작 도시에서 도시 1을 거쳐 도시 2로, 그리고 도시 3으로 이동 후 다시 돌아올 수 있는 다양한 경로가 존재합니다. 우리의 목표는 그 중에서 가장 짧은 거리의 경로를 찾아 출력하는 것입니다.
문제 해결을 위한 접근법
이 문제는 DFS(깊이 우선 탐색)를 활용한 백트래킹(Backtracking) 접근법으로 해결할 수 있습니다. 그러나 N이 10 이하로 제한되어 있기 때문에, 완전탐색(Brute Force) 기법을 사용해도 충분합니다. 이 문제는 어떤 경로를 갈지 결정하는 것이 가장 중요한데, 이는 주어진 거리 배열을 다루는 방법에 따라 결정됩니다.
알고리즘 단계
- 도시의 수를 기억합니다.
- 현재 도시를 기준으로 남은 도시들을 모든 경우의 수를 통해 순회합니다.
- 가장 적은 거리의 경로를 업데이트 합니다.
- 최종적으로 최소 거리를 반환합니다.
C# 코드 예시
using System;
class Salesman
{
static int N;
static int[,] dist;
static bool[] visited;
static int minCost = int.MaxValue;
static void Main(string[] args)
{
N = 4;
dist = new int[,] {
{ 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 }
};
visited = new bool[N];
visited[0] = true; // 시작 도시는 방문했습니다.
DFS(0, 0, 1); // 첫 번째 도시 방문
Console.WriteLine("최소 거리: " + minCost);
}
static void DFS(int currentCity, int cost, int count)
{
// 모든 도시를 방문한 경우
if (count == N)
{
// 돌아오는 거리 계산
cost += dist[currentCity, 0];
minCost = Math.Min(minCost, cost);
return;
}
// 다음 도시 탐색
for (int nextCity = 0; nextCity < N; nextCity++)
{
if (!visited[nextCity])
{
visited[nextCity] = true; // 방문한 도시로 표시
DFS(nextCity, cost + dist[currentCity, nextCity], count + 1);
visited[nextCity] = false; // 백트랙킹
}
}
}
}
코드 설명
위 코드는 DFS 백트래킹 기법을 사용하여 최소 거리를 찾는 예제입니다:
Main메서드: 도시 수와 거리 배열을 초기화 후 첫 번째 도시에서 DFS를 시작합니다.DFS메서드: 현재 도시에서 방문하지 않은 도시를 재귀적으로 탐색합니다. 모든 도시를 방문했을 경우, 시작 도시로 돌아가는 경우를 추가하여 최소 비용을 갱신합니다.
복잡도 분석
이 알고리즘의 시간 복잡도는 O(N!)입니다. 이는 모든 가능한 경로를 탐색하기 때문입니다. 하지만 N이 작기 때문에 실제로는 충분히 실행 가능합니다.
테스트 케이스
이제 이 알고리즘을 다양한 테스트 케이스로 검증해 보겠습니다:
// Test case 1
N = 3
dist = [[0, 10, 15],
[10, 0, 20],
[15, 20, 0]]
// Expected output: 35
// Test case 2
N = 5
dist = [[0, 20, 30, 10, 50],
[20, 0, 40, 30, 50],
[30, 40, 0, 30, 20],
[10, 30, 30, 0, 20],
[50, 50, 20, 20, 0]]
// Expected output: 90
결론
이번 코딩테스트 문제 풀이를 통해 세일즈맨의 고민을 해결했습니다. 알고리즘을 이해하고, C#을 통해 구현하면서 거리 배열을 어떻게 활용하는지 배웠습니다. 세일즈맨 문제는 알고리즘 경시 대회에서도 자주 출제되므로, 충분히 연습해보시길 바랍니다. 또한, 비슷한 문제를 다양한 접근법으로 풀어보는 것도 좋은 연습이 될 것입니다.
이번 포스팅이 유용했다면, 다음 포스팅도 기대해 주세요! 감사합니다.