[백준 2098번 / C++] 외판원 순회

비트마스킹과 dp를 활용한 문제이다. 

 

tsp 알고리즘은 완전 탐색으로 도시가 n개이면 시간 복잡도 n! 이 걸리는 np-hard문제로 널리 알려져있다. 그렇기 때문에 이미 탐색했던 경로에 대해서는 다시 방문해서 처음부터 재귀함수를 호출할 필요없이 비트마스킹과 메모이제이션을 활용해 기록했던 데이터값을 다시 들고와야 시간초과를 피할 수 있다. 

 

#접근방법

 

* dp [도시의 수][ 방문 비트] 

 

ex) [방문비트] -> 1100 : 4번째 도시와 3번째 도시를 방문했다는 뜻. 

 

ex.1) " 0 -> 1 -> 2 -> 3 (도시 방문 경로) "

 위의 방문 경로는 dp[3][1111(2진수)]의 배열의 주소를 참조하고 있으며
해당 배열에 다음 도시로 가야할 경로값 중 최소값을 더해주며 갱신해준다. 

즉, 완전탐색을 하던 도중 

ex.2) " 0 -> 2 -> 1 -> 3 (도시 방문 경로) "

만나게 된다면 위의 경로 또한 dp[3][1111(2진수)]의 배열의 주소를 참조하고 있다.

그러므로,
이미 저 경로에서 최소값은 ex.1) 에서 갱신되었기 때문에 이미 갱신 된 값이 있다면 그대로 들고와서 쓰면 된다는 뜻이다. 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std; 
int map[16][16]; 
int dp[16][1 << 16 ]; 
int n; 
int inf = 987654321; 
int tsp(int start, int visited) {
	if (visited == (1 << n ) - 1) {
		return map[start][0] ? map[start][0] : inf; 
	}
	int& ret = dp[start][visited]; 
	if (ret != -1)return ret; 
	ret = inf; 
	for (int i = 0; i < 16; i++) {
		if (visited & (1 << i)||map[start][i]==0)continue; 
		else {
			ret = min(ret, tsp(i, visited | (1 << i)) + map[start][i]); 
		}
	}
	return ret; 
}
int main() {
	
	cin >> n; 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j]; 
		}
	}
	memset(dp, -1, sizeof(dp)); 
	cout<< tsp(0, 1); 

}

2098번: 외판원 순회