모든 가능한 경로를 탐색하면 최대 16!의 시간이 걸려서 시간초과가 뜰 것이다.
더 효율적으로 처리하기 위해서 dp를 쓸 것이다.
현재까지 방문한 노드의 상태를 2진법 16자리수로 비트마스킹을 하고, 현재 방문한 점을 이용해서
dp[state][current] 이런식으로 쓸 것이다.
만약 이 dp값이 존재하며 그 이후는 탐색이 필요하지 않기 때문에 시간을 줄일 수 있다.
탐색은 dfs로 돌리면 된다.
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int N;
int w[100][100];
int dp[100000][100];
int big = 100000000;
int dfs(int state, int curr)
{
//printf("%d %d\n",state,curr);
if(dp[state][curr]!=0){
return dp[state][curr];
}
if(state == (1<<N)-1){
if(w[curr][1]==0) return big;
return w[curr][1];
}
dp[state][curr] = big;
int minv = big;
int ss = state;
for(int i=1;i<=N;i++)
{
if(ss%2==0) //i번 아직 방문안함
{
if(w[curr][i]!=0)
{
int ddd=pow(2,i-1);
int x = w[curr][i] + dfs(state+ddd,i);
if(minv>x) minv = x;
}
}
ss/=2;
}
dp[state][curr] = min(minv,dp[state][curr]);
return dp[state][curr];
}
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
scanf("%d",&w[i][j]);
}
}
printf("%d",dfs(1,1));
}해결 코드이다.
