작성자: 조광형
작성일: 2024년 11월 26일
문제 정의
“외판원 문제”는 주어진 도시들을 모두 방문하고 다시 시작점으로 돌아오는 최소 경로를 찾는 문제입니다.
이 문제는 컴퓨터 과학 및 최적화 이론에서 중요한 문제이며, 다양한 실제 문제에 응용될 수 있습니다.
외판원 문제는 특히 NP-완전 문제로 알려져 있으며, 효과적인 알고리즘을 통해 해결할 수 있는 방법을 탐구해 보겠습니다.
문제 설명
주어진 N개의 도시가 있으며, 각 도시 사이의 거리가 주어집니다. 외판원은
모든 도시를 한 번씩 방문한 후, 다시 시작 도시로 돌아와야 합니다.
최소 비용으로 모든 도시를 방문할 경로를 구하세요.
입력:
- 첫째 줄: 도시의 개수 N (1 ≤ N ≤ 20)
- 둘째 줄: N x N 행렬의 형태로 거리 정보.
(행렬의 i행 j열은 도시 i에서 도시 j까지의 거리)
출력:
- 최소 비용
문제 접근 방법
이 문제의 해결을 위해 다이나믹 프로그래밍(Dynamic Programming)과 비트 마스킹(Bit Masking) 기법을 사용합니다.
다이나믹 프로그래밍을 통해 서브 문제를 해결하고, 비트 마스킹을 통해 도시 방문 여부를 관리합니다.
N개의 도시가 있을 때, 각 도시의 방문 상태는 비트로 표현할 수 있습니다.
예를 들어, N=4의 경우 0000은 어떤 도시도 방문하지 않은 상태, 1111은 모든 도시를 방문한 상태를 의미합니다.
이를 통해 각 서브 문제에서 이전에 계산된 값을 활용하여 최소 비용을 계산할 수 있습니다.
알고리즘 설명
1. **비트마스킹 설정**:
각 도시의 상태를 비트로 표현합니다. 예를 들어, 4개의 도시가 있으면 0b0000부터 0b1111까지 표현할 수 있습니다.
이 비트마스크를 사용하여 방문한 도시를 추적할 수 있습니다.
2. **재귀 호출**:
현재 도시와 방문한 도시의 비트마스크를 인자로 받고, 모든 도시를 방문하기 위한 최소 비용을 계산합니다.
3. **메모이제이션**:
이전에 계산한 결과를 저장하여 중복 계산을 줄입니다. 상태는 `(현재 도시, 방문한 도시의 비트마스크)`로 저장합니다.
4. **최종 경로 계산**:
모든 도시를 방문한 경우, 시작 도시로 돌아오는 비용을 더하여 최소 경로를 반환합니다.
C++ 코드 구현
#include
#include
#include
#include
using namespace std;
int N; // 도시의 개수
int dist[20][20]; // 거리 행렬
int dp[1 << 20][20]; // 메모이제이션
int tsp(int mask, int pos) {
// 모든 도시를 방문했으면 시작 도시로 돌아간다
if (mask == (1 << N) - 1) {
return dist[pos][0]; // 시작 도시로의 거리
}
// 이미 계산된 결과가 있으면 이를 즉시 반환
if (dp[mask][pos] != -1) {
return dp[mask][pos];
}
int ans = INT_MAX; // 초기값은 무한대를 설정
for (int city = 0; city < N; city++) {
// 도시가 방문되지 않았다면 다음 도시로 이동
if ((mask & (1 << city)) == 0) {
int newAns = dist[pos][city] + tsp(mask | (1 << city), city);
ans = min(ans, newAns);
}
}
return dp[mask][pos] = ans; // 결과 저장
}
int main() {
// 도시의 개수를 입력받는다
cout << "도시의 개수를 입력하세요: ";
cin >> N;
// 거리 행렬 입력
cout << "거리 행렬을 입력하세요:" << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> dist[i][j];
}
}
// 메모이제이션 배열 초기화
memset(dp, -1, sizeof(dp));
// 최소 비용 계산 및 출력
int result = tsp(1, 0); // 시작할 때 첫 번째 도시를 방문
cout << "최소 비용: " << result << endl;
return 0;
}
결론
외판원 문제는 알고리즘 및 데이터 구조의 중요한 예제 중 하나로,
다이나믹 프로그래밍 기법을 통해 효과적으로 해결할 수 있습니다.
이 문제를 통해 비트 마스킹과 메모이제이션이 어떻게 결합되어 강력한 해결책을 제공하는지를 이해할 수 있었습니다.
실제 코딩 인터뷰에서도 자주 등장하는 문제이므로 충분한 연습을 통해 숙련도를 높이는 것이 중요합니다.