코딩테스트에서 자주 출제되는 문제 중 하나가 바로 ‘외판원의 순회 문제’입니다. 이 문제는 주어진 여러 도시들 사이를 여행하며 돌아오는 경로를 최소 비용으로 찾는 문제입니다. 이 문제는 NP-완전 문제에 속하여, 최적해를 찾는 것이 매우 어렵습니다. 따라서, 다양한 탐색 알고리즘을 통해 근사적인 해를 찾거나, 동적 프로그래밍(DP)을 이용하여 최적해를 찾는 방식이 일반적입니다.
문제 정의
n개의 도시가 있으며, 각 도시는 서로 다른 다른 도시와 연결되어 있다고 가정합니다. 각 도시 간의 이동 비용이 주어질 때, 모든 도시를 한 번씩 방문하고 출발 도시로 되돌아오는 최소 비용의 순회를 출력하시오.
입력
- 첫 번째 줄에는 도시의 수 n (1 ≤ n ≤ 10)이 주어진다.
- 다음 n개의 줄에는 n x n 크기의 인접 행렬이 주어진다. 각 행렬의 원소는 두 도시 간의 이동 비용을 나타낸다. 이동 비용이 없는 경우에는 0이 주어진다.
출력
모든 도시를 한 번씩 방문하고 다시 출발지로 돌아오는 최소 비용을 출력한다.
예제
입력:
4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0
출력:
80
문제 해결 과정
1. 문제 분석
문헌에 따르면 이 문제는 NP-완전 문제로 알려져 있어, 모든 가능한 경로를 시도하는 완전 탐색 방식으로 접근할 수 있습니다. 그러나 도시의 수가 10개 이하일 때는 이러한 방식이 실효성이 있다는 것을 보여줄 수 있습니다. 각 도시를 한 번씩 방문하는 경우의 수는 (n-1)! 이기 때문에, n이 10일 경우 9! = 362880 이라는 충분히 계산 가능한 범위입니다.
2. 알고리즘 선택
여기서는 백트래킹 기법을 통해 모든 경로를 탐색하여 최소 비용을 계산하는 알고리즘을 선택하겠습니다. 이 알고리즘은 현재 도시를 기준으로 가능한 경로를 재귀적으로 탐색하며, 더 이상 진행할 수 없는 경우에는 이전 단계로 돌아가서 다른 경로를 시도합니다. 이를 통해 모든 경우의 수를 고려하여 최소 비용을 찾을 수 있습니다.
3. C# 코드 구현
using System;
class Program
{
static int n; // 도시의 수
static int[,] cost; // 이동 비용 행렬
static bool[] visited; // 방문 도시 체크
static int minCost = int.MaxValue; // 최소 비용
static void Main(string[] args)
{
n = int.Parse(Console.ReadLine());
cost = new int[n, n];
visited = new bool[n];
for (int i = 0; i < n; i++)
{
var line = Console.ReadLine().Split();
for (int j = 0; j < n; j++)
{
cost[i, j] = int.Parse(line[j]);
}
}
visited[0] = true; // 시작 도시 방문 표시
FindPath(0, 0, 1); // 현재 도시(0), 현재 비용(0), 방문 도시 수(1)
Console.WriteLine(minCost);
}
static void FindPath(int currentCity, int currentCost, int count)
{
if (count == n && cost[currentCity, 0] != 0) // 모든 도시를 방문했다면
{
minCost = Math.Min(minCost, currentCost + cost[currentCity, 0]);
return;
}
for (int nextCity = 0; nextCity < n; nextCity++)
{
if (!visited[nextCity] && cost[currentCity, nextCity] != 0)
{
visited[nextCity] = true;
FindPath(nextCity, currentCost + cost[currentCity, nextCity], count + 1);
visited[nextCity] = false; // 백트래킹
}
}
}
}
4. 코드 설명
위의 코드는 도시 수를 입력받아 주어진 인접 행렬을 생성합니다. 그런 다음, FindPath 함수를 사용하여 모든 경로를 탐색합니다. 이 함수의 주요 매개변수는 다음과 같습니다:
- currentCity: 현재 방문 중인 도시
- currentCost: 지금까지의 이동 비용
- count: 현재까지 방문한 도시 수
기본적으로 시작 도시는 방문 표시가 되어 있으며, 모든 도시를 방문하게 되면 처음 도시로의 경비를 계산하고 최소 비용과 비교합니다. 만약, 더 줄일 수 있다면 minCost를 갱신합니다.
5. 시간 복잡도
이 문제의 시간 복잡도는 O(n!)입니다. 모든 도시를 방문하는 조합을 탐색하므로 도시 수가 증가할수록 계산량이 기하급수적으로 증가하게 됩니다.
결론
이번 강좌를 통해 외판원의 순회의 최소 비용을 찾는 문제를 C#로 해결하는 방법을 다루었습니다. 해당 문제는 기본적인 백트래킹 알고리즘을 통해 해결할 수 있으며, 더 좋은 효율성을 위해 다양한 최적화 기법과 동적 프로그래밍을 활용할 수도 있습니다. 향후에는 이러한 기법들에 대해서도 다루어보도록 하겠습니다.