O(N!)
의 시간이 걸려 time limit이 발생cache[start][state]
를 이용한 Memoization 구현시 시간 복잡도는 O(N2 x 2N)start : 출발하려는 도시의 번호,
state : 현재 이동한 도시들을 나타낸 길이가 N인 String 배열 ex) "110"
cache[start][state]
배열을 이용하지만 state변수가 int형 정수 ex) 6 = 1102
DFS(int start, int state)
의 함수를 사용하여 경우의 수를 계산.DFS(0, 1)
만 호출하여도 답을 구할 수 있다.N이 4일때
W[0][1] + W[1][2] + W[2][3] + W[3][0] = W[1][2] + W[2][3] + W[3][0] + W[0][1]
이므로
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <cstring>
#include <map>
#define MAX 2000000000
using namespace std;
int N;
vector<vector<int>> adj(16);
int cache[16][1<<16];
bool bitCheck(int state, int i){ // state의 i번째 bit가 1이면 true, 0이면 false를 반환
return (state & 1<<i) ? true : false;
}
int DFS(int start, int state){
if(state == (1<<N)-1) return adj[start][0];
if(cache[start][state] != MAX) return cache[start][state]; // cache[start][state]의 값이 존재한다면
for(int i=0; i<N; i++){
if(bitCheck(state, i)) continue; // state의 i번째 bit가 1이면 continue
if(adj[start][i] == 0) continue; // 도시 i에서 도시 j로 갈 수 없으면 continue
int ret = DFS(i, state | 1<<i);
if(ret == 0) continue;
cache[start][state] = min(cache[start][state], ret + adj[start][i]);
}
return cache[start][state];
}
int main(){
scanf("%d", &N);
for(int i=0; i<N; i++)
for(int j=0; j<N; j++){
int weight;
scanf("%d", &weight);
adj[i].push_back(weight);
}
fill(&cache[0][0], &cache[N-1][1<<N], MAX); // cache의 모든 값을 MAX로 채운다
int first = 1; // 초기 state의 값은 1
int mins = DFS(0, first);
printf("%d \n", mins);
}
for(int i=0; i<N; i++) cache[i][state|1<<i] = min(cache[i][state|1<<i], cache[start][state] + adj[start][i]);