백준(BOJ) 2098 외판원 순회 **

외판원 순회 알고리즘에 대해 공부하고 푸는 것을 추천한다.

[알고리즘/알고리즘 정리] - 외판원 순회 문제(Traveling Salesperson Problem, TSP)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#define MAX 17
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<float, float> pf;

int n,w[MAX][MAX],dp[MAX][1<<16];
vector<int> v;

int tsp(int cur,int visit)
{
    if(visit==(1<<n)-1)
        return w[cur][1];
    // 모든 정점을 모두 방문하고 마지막으로 원점(1)으로 돌아왔을 때
    
    if (dp[cur][visit] > 0)
        return dp[cur][visit];
    // 이전에 방문한 케이스의 경우 바로 return한다.
    
    int ret=INF;
    
    for(int i=2;i<=n;i++)
    {
        if(w[cur][i]==0)continue;
        // 경로가 없는 경우
        
        if((visit&(1<<(i-1)))!=0)continue;
        // 방문한 도시인 경우
        
        int tmp=w[cur][i]+tsp(i,visit+(1<<(i-1)));
        ret = min(ret, tmp);
        // 다음 도시들을 선택하여 이동하였을때 가장 적은 비용이 드는 경로 선택
    }
    return dp[cur][visit]=ret;
    // 디피에 결과를 저장하고 return한다.
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int k=1;k<=n;k++)
            scanf("%d",&w[i][k]);
    printf("%d",tsp(1,1));
    return 0;
}