문제
문제 설명
외판원 순회(TSP : Traveling Salesperson Problem) 문제는 도시들이 있고 어떤 도시에서 출발하여 모든 도시를 돌고 다시 출발 도시로 돌아왔을 때 드는 최소비용을 구하는 문제이다.
구현
백준에 외판원 순회 문제가 또 있는데 그 문제와 똑같이 생겼지만 시간제한과 메모리 제한이 절반이다.
이 문제에서는 DP와 비트마스킹을 사용하여 풀어야 한다.
DP배열로 특정 도시들을 방문한 상태일 때, 나머지 도시들을 방문하고 출발 도시로 돌아왔을 때의 최소 비용을 저장하고, 비트마스킹은 특정 도시를 방문했다는 상태를 저장할 때 사용한다.
2차원 배열로 선언된 DP[i][j] 가 의미하는 것은 현재 있는 도시가 i이고, 방문한 도시들의 집합이 j 일때, 방문하지 않은 나머지 도시들을 모두 방문한 뒤 출발 도시로 돌아올 때 드는 최소 비용이다.
이런 식으로 풀어도 문제가 풀리는 이유는 출발 도시가 달라져도, 경로가 같다면 최소 비용이 같다는 점을 알아야 한다.
어떤 도시에서 출발해도 모든 도시를 돌고 다시 출발했던 도시로 돌아오는 과정에서 사이클이 발생하기 때문이다.
도시가 5개가 있다고 했을 때 1 -> 2 -> 3 -> 5 -> 4 -> 1 와 1 -> 3 -> 2 -> 5 -> 4 -> 1 이렇게 두가지 경로가 있다고 했을 때 중복되는 경로가 있기 때문에 이 계산을 중복되게 하지 않게 하기 위함이다.
DP 배열은 2차원으로 선언을 했는데 크기를 선언해줘야한다.
dp = new int[n][(1 << n) - 1];위에서 말했듯이 현재 있는 도시는 입력으로 들어오는 n 만큼 있을 거고 방문한 도시들의 집합이 뒤에 들어와야 하는데 경우의 수를 확인하기 위해서는 2^n - 1 만큼이 필요하니 (1 << n) - 1 만큼 선언해준다.
그 후 dp배열의 값들을 모두 -1 로 초기화 해주고 재귀함수를 시작한다.
tsp 라고 선언된 함수는 현재 내가 있는 도시의 번호와 방문한 도시의 집합들을 인자로 받는다.
public static int tsp(int cur, int visit) {
//내부 로직 구현
}그 후에 함수의 시작 부분에 모든 도시를 방문한 경우를 처리해준다.
//모든 도시를 방문한 경우
if (visit == (1 << n) - 1) {
//현재도시 cur -> 출발도시 0 으로 가는 경로가 없다면 INF 리턴
if(weight[cur][0] == 0)
return INF;
return weight[cur][0];
}현재 방문한 도시가 (1 << n) - 1 과 같다는 것은 모든 비트가 1로 켜졌다는 것이므로 모든 도시를 방문했다는 뜻이다.
이때 위치한 cur 이라는 도시에서 출발 도시인 0번 인덱스로 돌아오는 비용이 0이라면, 돌아올 수 없다는 뜻이므로 INF를 반환하고, 그렇지 않다면 출발 도시로 가는 비용인 weight[cur][0]을 반환해준다.
만약 dp[cur][visit] 이 초기 값인 -1이 아니라면, 이미 방문한 경로들이기 때문에 해당 비용을 반환해준다.
/이미 방문한 경로라면 해당 비용 리턴
if(dp[cur][visit] != -1)
return dp[cur][visit];이렇게 두가지 상황을 모두 처리했다면 이제 dp에 들어갈 값을 계산을 해주어야 한다.
일단 dp[cur][visit]을 INF로 초기화한다.
그 후에 i를 0부터 n까지 반복하고 visit 과 AND 연산을 통해 방문하지 않은 도시들을 확인한다.
dp[cur][visit] = INF;
for(int i = 0; i < n; i++){
//visit & (1 << i) == 0 이라면 i번째 도시를 방문하지 않았다는 뜻
if((visit & (1 << i)) == 0 && weight[cur][i] != 0){
//재귀함수로 i에서 시작하는 방향을 탐색, visit에 (1 << i)를 OR 연산을 해주면서 해당 위치를 방문했다는 표시
dp[cur][visit] = Math.min(tsp(i, visit | (1 << i)) + weight[cur][i], dp[cur][visit]);
}
}dp[cur][visit] 값은 위의 코드와 같이 다음 도시로 이동하고, 그 도시를 방문 처리한 후, 재귀적으로 다시 호출한 값인 tsp(i, visit | (1 << i)) 와 현재 도시에서 i로 이동하는 비용을 더한 값과 현재 위치인 cur 에서 visit까지의 dp 값 중 작은 값을 골라주면 된다.
코드
import java.io.*;
import java.util.*;
public class Main_2098 {
static int n;
static int[][] weight;
static int[][] dp;
static int result;
static final int INF = 100_000_000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
StringTokenizer st = null;
weight = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
weight[i][j] = Integer.parseInt(st.nextToken());
}
}
dp = new int[n][(1 << n) - 1];
for (int i = 0; i < n; i++) {
Arrays.fill(dp[i], -1);
}
System.out.println(result = tsp(0, 1));
}
public static int tsp(int cur, int visit) {
//모든 도시를 방문한 경우
if (visit == (1 << n) - 1) {
//현재도시 cur -> 출발도시 0 으로 가는 경로가 없다면 INF 리턴
if(weight[cur][0] == 0)
return INF;
return weight[cur][0];
}
//이미 방문한 경로라면 해당 비용 리턴
if(dp[cur][visit] != -1)
return dp[cur][visit];
dp[cur][visit] = INF;
for(int i = 0; i < n; i++){
//visit & (1 << i) == 0 이라면 i번째 도시를 방문하지 않았다는 뜻
if((visit & (1 << i)) == 0 && weight[cur][i] != 0){
//재귀함수로 i에서 시작하는 방향을 탐색, visit에 (1 << i)를 OR 연산을 해주면서 해당 위치를 방문했다는 표시
dp[cur][visit] = Math.min(tsp(i, visit | (1 << i)) + weight[cur][i], dp[cur][visit]);
}
}
return dp[cur][visit];
}
}
