세일즈맨의 고민은 전통적인 알고리즘 문제 중 하나로, “외판원 순회 문제” 또는 “여행하는 세일즈맨 문제”라고도 불린다.
이 문제는 여러 도시가 있을 때, 세일즈맨이 모든 도시를 방문한 후 다시 출발 도시로 돌아오는 가장 짧은 경로를 찾는 것이다.
이 문제는 조합 최적화(combinatorial optimization) 문제에 속하며 NP-hard로 분류된다.
따라서, 작은 데이터 셋은 브루트 포스(brute force) 알고리즘으로 해결할 수 있지만, 큰 데이터 셋은 더 효율적인 접근 방법이 필요하다.
문제 설명
N개의 도시가 주어지고, 각 도시 간의 거리 행렬이 주어진다. 목표는 세일즈맨이 각 도시에 한 번씩 방문한 후 출발 지점으로 돌아오는 가장 짧은 경로의 거리 합을 구하는 것이다.
다음은 문제의 형식이다.
입력:
N (도시의 수)
거리 행렬 (nxn 행렬)
출력:
최소 경로의 길이
예제
입력 예시:
4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0
출력 예시:
80
문제 해결 과정
문제를 해결하기 위한 여러 가지 접근법이 있으며, 여기서는 브루트 포스 알고리즘과 동적 프로그래밍(DP) 두 가지 방법을 사용하여 이 문제를 해결해보겠다.
1. 브루트 포스 방법
브루트 포스 방법은 모든 가능한 경로를 탐색하여 최단 경로를 찾는 방식이다.
모든 도시의 순열을 생성하여 각 경로 거리를 계산하고, 이 중에서 최소 거리를 찾는다.
알고리즘 설명
- 모든 도시의 순열을 생성한다.
- 각 순열에 대해 전체 거리 값을 계산한다.
- 계산된 거리 중 최소 거리 값을 찾는다.
C++ 코드 예시
#include
#include
#include
#include
using namespace std;
int calculateDistance(const vector>& dist, const vector& path) {
int totalDistance = 0;
for (int i = 0; i < path.size() - 1; i++) {
totalDistance += dist[path[i]][path[i + 1]];
}
totalDistance += dist[path.back()][path[0]]; // Return to start
return totalDistance;
}
int main() {
int N;
cin >> N;
vector> dist(N, vector(N, 0));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> dist[i][j];
vector cities(N);
for (int i = 0; i < N; i++) cities[i] = i;
int minDistance = INT_MAX;
do {
int currentDistance = calculateDistance(dist, cities);
minDistance = min(minDistance, currentDistance);
} while (next_permutation(cities.begin() + 1, cities.end())); // Fix first city
cout << minDistance << endl;
return 0;
}
2. 동적 프로그래밍(DP) 방법
동적 프로그래밍 방법은 메모리를 효율적으로 사용하는 방법이다.
도시를 비트마스크로 표현하여 각 도시의 방문 여부를 나타내고, 재귀 함수와 메모이제이션을 이용하여 최단 경로를 계산한다.
이 경우 복잡도는 O(n^2 * 2^n)로 줄어든다. 다음은 동적 프로그래밍 솔루션의 설명이다.
알고리즘 설명
- 비트마스크를 사용하여 각 도시의 방문 여부를 나타낸다.
- 최소 비용 테이블을 초기화하고 0으로 설정한다.
- 재귀 함수를 통해 가능한 경로를 탐색하며 최소 거리 값을 갱신한다.
C++ 코드 예시
#include
#include
#include
using namespace std;
int tsp(int pos, int visited, const vector>& dist, vector>& memo) {
if (visited == ((1 << dist.size()) - 1)) {
return dist[pos][0]; // Return to the start city
}
if (memo[pos][visited] != -1) {
return memo[pos][visited];
}
int minCost = INT_MAX;
for (int city = 0; city < dist.size(); city++) {
if ((visited & (1 << city)) == 0) {
int newCost = dist[pos][city] + tsp(city, visited | (1 << city), dist, memo);
minCost = min(minCost, newCost);
}
}
return memo[pos][visited] = minCost;
}
int main() {
int N;
cin >> N;
vector> dist(N, vector(N, 0));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> dist[i][j];
vector> memo(N, vector((1 << N), -1));
cout << tsp(0, 1, dist, memo) << endl;
return 0;
}
결론
이 강좌에서는 C++로 구현된 세일즈맨의 고민 문제를 통해 문제 정의, 예제,
그리고 문제 해결을 위한 브루트 포스 및 동적 프로그래밍 방법을 상세히 알아보았다.
주의할 점은 브루트 포스 방법은 도시의 수가 작을 때만 사용해야 하며, 도시의 수가 증가할수록 동적 프로그래밍 방법을 사용하는 것이 더 효율적이다.
이러한 알고리즘 문제들은 실제 코딩 테스트 및 면접에서 자주 등장하므로, 충분한 연습이 필요하다.