외판원 순회
•
여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것이다.
•
완전탐색으로도 해결할 수 있지만 이동의 수가 어마어마하므로 사용하지 않는다.
•
중복되는 경로의 조사를 막기 위해 DP memoization 기법을 사용한다.
비트마스킹
•
bit 연산이기 때문에 다른 자료구조를 사용하는 것 보다 훨씬 빠르게 동작되고, 코드도 간결하다.
•
TSP 문제의 경우 큰 수를 표현해야하기 때문에 큰 공간복잡도가 필요하다.
•
비트 마스킹을 사용하면 메모리 사용을 줄이고, 성능향상을 할 수 있다.
•
예 16 개의 지점 중 1, 3, 4, 5 번을 방문 → 0000 0000 0001 1101
2098 외판원 순회
DP 와 비트마스크의 사용
•
DP 는 특정 도시를 방문했을 때의 최소 비용을 저장해 놓는다.
•
비트 마스크는 특정 도시를 방문한 상태를 저장한다.
코드
틀렸습니다 코드
시간초과 코드
최종 코드
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N;
static int[][] W;
static int[][] dp;
static final int INF = 1000000000;
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
W = new int[N][N];
dp = new int[1 << N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
W[i][j] = Integer.parseInt(st.nextToken());
}
}
init();
int result = TSP(1, 0);
System.out.println(result);
}
public static void init() {
for (int i = 0; i < (1 << N); i++) {
for (int j = 0; j < N; j++) {
dp[i][j] = -1;
}
}
}
public static int TSP(int bit, int current) {
if (bit == (1 << N) - 1) {
return W[current][0] == 0 ? INF : W[current][0];
}
if (dp[bit][current] != -1) {
return dp[bit][current];
}
dp[bit][current] = INF;
for (int i = 0; i < N; i++) {
if ((bit & (1 << i)) == 0 && W[current][i] != 0) {
dp[bit][current] = Math.min(dp[bit][current], TSP(bit | (1 << i), i) + W[current][i]);
}
}
return dp[bit][current];
}
}
Java
복사
초기화 후의 dp 배열은 아래와 같다.
입력은 첫번째 예시를 기준으로 한다.
public static void init() {
for (int i = 0; i < (1 << N); i++) {
for (int j = 0; j < N; j++) {
dp[i][j] = -1;
}
}
}
Java
복사
dp[0][0], dp[0][1], dp[0][2], dp[0][3] = -1, -1, -1, -1
dp[1][0], dp[1][1], dp[1][2], dp[1][3] = -1, -1, -1, -1
dp[2][0], dp[2][1], dp[2][2], dp[2][3] = -1, -1, -1, -1
...
dp[15][0], dp[15][1], dp[15][2], dp[15][3] = -1, -1, -1, -1
Java
복사
TSP 함수
public static int TSP(int bit, int current) {
if (bit == (1 << N) - 1) {
return W[current][0] == 0 ? INF : W[current][0];
}
if (dp[bit][current] != -1) {
return dp[bit][current];
}
dp[bit][current] = INF; // 초기값 재설정
for (int i = 0; i < N; i++) {
if ((bit & (1 << i)) == 0 && W[current][i] != 0) {
dp[bit][current] = Math.min(dp[bit][current], TSP(bit | (1 << i), i) + W[current][i]);
}
}
return dp[bit][current];
}
Java
복사
•
bit는 현재 방문한 도시들을 나타내는 비트마스크이다.
current는 현재 도시다.
•
모든 도시를 방문했다면, 시작점으로 돌아가는 비용을 반환한다.
◦
이미 계산된 경우, dp[bit][current] 를 반환한다.
◦
아직 계산되지 않은 경우, 가능한 모든 도시를 방문하면서 최적 비용을 갱신한다.
•
만약 현재 bit = 1 이라면,
◦
도시 0 만 방문한 상태이다.
◦
current = 0 현재 위치한 도시는 0 번이다.
◦
첫번째 loop
▪
i = 0
▪
if ((bit & (1 << i)) == 0 : 현재 상태에서 i 번째 도시가 방문되지 않았음을 의미한다.
▪
W[current][i] != 0 : 현재 도시에서 i 번째 도시로 가는 길이 존재함을 의미한다.
•
문제에서 갈 수 없는 경우 0 으로 지정했다.
▪
(1 << 0) = 0001 이므로 false 이다.
◦
두번째 loot
▪
i = 1
▪
1 << 1 = 0010 이고, (bit & 0010) == 0 이므로 도시 1 은 아직 방문되지 않았다.
▪
W[0][1] = 10 이므로, 도시에서 1 로 가는 길이 존재한다.
▪
dp[bit][current] 를 갱신한다.
▪
TSP(bit | (1 << i), i) 를 호출한다.
•
도시 1 을 방문한 새로운 상태에서의 최적 비용을 계산한다.
•
TSP(0011, 1) 이 된다.
▪
dp[bit][current] = Math.min(dp[bit][current], TSP(0011, 1) + W[0][1]);
◦
이를 반복한다. 다 돌게 되면, TSP(0001, 0) 이 된다.