문제 설명
N명의 도시를 가진 세일즈맨이 있고, 이 세일즈맨은 모든 도시를 한 번씩 방문하고 다시 출발 도시로 돌아와야 합니다.
세일즈맨은 각 도시 간의 거리 정보가 주어지며, 최단 경로를 찾는 것이 목표입니다.
이 문제를 해결하기 위해서는 백트래킹, 동적 프로그래밍 또는 비트마스크를 이용한 최단 경로 탐색 알고리즘을 사용할 수 있습니다.
입력 형식
첫째 줄에는 도시의 개수 N이 주어진다. 이어서 N x N 크기의 행렬이 주어지며,
matrix[i][j]는 도시 i에서 도시 j까지의 거리를 나타낸다.
단, matrix[i][i]는 항상 0이다.
출력 형식
세일즈맨이 모든 도시를 한 번씩 방문하고 출발지로 돌아오기 위한 최소 비용을 출력한다.
예제
입력:
4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0
출력:
80
문제 풀이 과정
본 문제는 전형적인 외판원 문제(TSP, Traveling Salesman Problem)로,
세일즈맨이 모든 도시를 방문한 뒤 출발지로 돌아오는 가장 짧은 경로를 찾는 문제이다.
이 문제는 NP-완전 문제로, 도시의 수가 많아질수록 해를 찾기 위한 계산량이 기하급수적으로 증가한다.
이에 따라 여러 가지 접근 방법을 고려할 수 있다.
1. 백트래킹(Backtracking)
백트래킹은 모든 경로를 탐색하는 방식으로, 재귀적으로 모든 가능한 경로를 탐색하며
최적의 경로를 찾는 방식이다. 하지만 도시의 수가 커질수록 계산 시간이 늘어난다.
2. 동적 프로그래밍(Dynamic Programming)
동적 프로그래밍을 이용한 방법은 메모이제이션 기법을 활용하여 이미 계산된 경로의 최단 거리 값을 저장
해 중복 계산을 방지하는 방법이다.
이 방법론에 따라 특정 도시 집합에 대한 최소 비용을 저장하고
서브 문제를 해결하여 전체 문제의 해결책을 구성한다.
3. 비트마스크(Bitmasking)
비트마스킹은 도시 각각을 비트로 표현하여 모든 방문 상태를 관리하는 기법이다.
이를 통해 세일즈맨이 어떤 도시를 방문했는지를 효율적으로 관리할 수 있다.
이 방법은 동적 프로그래밍과 조합하여 사용할 때 매우 효과적이다.
알고리즘 구현
1. 비트마스킹을 이용한 동적 프로그래밍
import java.util.Arrays;
public class TravelingSalesman {
static final int INF = Integer.MAX_VALUE;
static int[][] dist;
static int[][] dp;
static int n;
public 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}
};
// DP 배열 초기화
dp = new int[n][1 << n];
for (int[] row : dp) {
Arrays.fill(row, -1);
}
// 최단 경로 계산
int result = tsp(0, 1);
System.out.println("최소 비용: " + result);
}
static int tsp(int pos, int mask) {
if (mask == (1 << n) - 1) { // 모든 도시를 방문한 경우
return dist[pos][0]; // 시작 도시로 돌아감
}
if (dp[pos][mask] != -1) {
return dp[pos][mask]; // 메모이제이션된 값 반환
}
int ans = INF;
// 모든 도시를 순회
for (int city = 0; city < n; city++) {
if ((mask & (1 << city)) == 0) { // 도시를 방문하지 않았다면
ans = Math.min(ans, dist[pos][city] + tsp(city, mask | (1 << city)));
}
}
return dp[pos][mask] = ans; // 현재 상태 메모이제이션
}
}
결론
본 문제는 세일즈맨이 모든 도시를 한 번씩 방문하고 다시 출발 도시로 돌아오는 최단 경로를 찾는 대표적인
경로 최적화 문제로, 다양한 알고리즘으로 접근 가능하다.
비트마스킹과 동적 프로그래밍을 활용한 이번 구현은 도시 수가 적을 경우 빠른 계산이 가능하며,
다수의 도시를 처리하기 위한 다른 기법의 사용도 가능하다.
이와 같은 문제를 통해 알고리즘적 사고를 기르는 것이 중요하며,
코딩 면접 대비와 실제 프로젝트에서도 매우 유용하게 사용될 것이다.
참고 문헌
- Introduction to Algorithms, Thomas H. Cormen 등의 저서
- Online Resources on Dynamic Programming and Traveling Salesman Problem