2098 TSP
알고리즘(외판원 순회, DP, 비트마스크)
1
2
3
4
5
1. 비트마스크로 각 비트마다 하나의 도시라고 치고, 검사를 함.
2. 방문하지 않았고, 갈수 있는 도시를 방문하는 식으로 끝까지감.
-> 끝까지 갔을 때 다시 돌아갈 수 있는 길이 있으면 그 값 반환, 없으면 IMPOSSIBLE 반환
-> 그 전 재귀로 돌아와서 가장 최솟값을 dp[current][bitMask] 에 저장함.
3. 각 재귀 처음엔 돌아갈 수 마지막인지 확인하고, 이미 방문됐는지 확인한다.
새겨둘 점.
1
2
3
4
5
6
7
8
9
10
11
1. 모든 출발점에 대해 실행할 필요는 없다.
-> 최소로 가능한 경로가 있을 때, 어디서 출발하든 그 값은 같기 때문에.
2. 끝까지 갔을 때, 그때부터 값을 하나씩 더해오는 식으로 계산한다.
-> 값을 들고가면 INFINITY값과 충돌을 일으켜 잘못된 값이 반환될 수 있게됨.
-> 또 이렇게하면 자동으로 dp엔 이후 경로의 최솟값이 저장됨.
3. 따라서 각 단계에서 최솟값이 INFINITY 값이라 하더라도 무조건 dp에 저장하자.
-> INFINITY값이 저장됐다는 거는, 현재상태에서 순회할 수 있는 길이 없다는 뜻이므로.
4. INFINITY값을 지정할 땐, 현재 value값을 더해도 오버플로우가 발생하지 않도록 지정해둘 필요가 있다.
5. 비트마스크로 각 도시가 이미 방문됐는지 확인하는 코드는 다음과 같다.
bitMask & (1 << i)
이미 방문됐다면 이 값은 참을 가리키게 된다. ( 1011 & 0010 => 0010 => 참 / 1011 & 0100 => 0000 => 거짓)
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstring>
#define MAX_TOWN 16
#define INFINITY 2000000123
using namespace std;
bool check[MAX_TOWN];
int dp[MAX_TOWN][1 << MAX_TOWN];
int map[MAX_TOWN][MAX_TOWN];
int numOfTown, start, endBit;
int getMinValue(int current, int bitMask);
int min(int a, int b);
int main() {
cin >> numOfTown;
for (int i = 0; i < numOfTown; i++)
for (int j = 0; j < numOfTown; j++) {
cin >> map[i][j];
}
endBit = (1 << numOfTown) - 1;
memset(dp, -1, sizeof(dp));
check[0] = true;
start = 0;
cout << getMinValue(0, 1);
}
int min(int a, int b) {
return a < b ? a : b;
}
int getMinValue(int current,int bitMask) {
if (bitMask == endBit) {
if (map[current][start] == 0)
return INFINITY;
return map[current][start];
}
if (dp[current][bitMask] != -1)
return dp[current][bitMask];
int tempMin = INFINITY;
for (int i = 0; i < numOfTown; i++) {
if (!check[i] && map[current][i] != 0) {
check[i] = true;
tempMin = min(tempMin, map[current][i] + getMinValue(i, bitMask + (1 << i)));
check[i] = false;
}
}
return dp[current][bitMask] = tempMin;
}