[ 백준 BOJ ] 2098 번 - 외판원 순회 (C++)

https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

TSP문제이다. 여러 시행착오 끝에 dp[도시 번호][비트필드]까지 알아냈지만 너무 지쳤는지 포기하고

https://hagisilecoding.tistory.com/150 이 블로그의 도움을 받아 풀었다.

이 블로그와 다른 점은 입력으로 모든 도시끼리 이어지지 않는다는 것이다. 따라서 이어지지 않은 도시의 경우 따로 예외적으로 다뤄야한다.

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <vector>
#include <set>

#define endl '\n'
#define ll long long
#define pii pair<int, int>

using namespace std;

int N;
int edge[18][18];
int dp[18][1<<18];

int TSP(int c, int bit){
    if(dp[c][bit]!=-1){
        return dp[c][bit];
    }
    dp[c][bit]=987654321;
    if(bit==((1<<N)-1)){
        if(edge[c][0]!=0)
            return dp[c][bit]=edge[c][0];
        else return dp[c][bit];
    }
    for(int i = 1; i<N; i++){
        if(!(bit&(1<<i))){
            int nbit = (bit|(1<<i));
            if(edge[c][i]!=0){
                dp[c][bit] = min(dp[c][bit],TSP(i,nbit)+edge[c][i]);
            }
        }
    }
    return dp[c][bit];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;
    int tmp;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin>>edge[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    cout<<TSP(0,1)<<endl;
    return 0;
}