2098번(다시 풀어보기)

2098번 - 외판원 순회

음..TSP 문제를 완전탐색 말고 비트마스크로 연습하려고 풀어봤는데 생각보다 헷갈린다.

DP 점화식을 보고 문제를 풀었는데, 코드 짜는 과정에서 실수가 발생했다. 아직 비트마스크 연습이 더 필요하다.

( http://www.qukihub.com/post/traveling-salesperson-problem-tsp 이 블로그를 참고했다. )

D[current][visited] = 현재 위치가 current이고 방문했던 도시들이 visited일 때, 부분 경로(집합)최솟값 

으로 놓고 점화식 문제를 풀었다.

기본 로직은 결국 완전탐색은 중복되는게 발생하기 때문에 DP로 풀 수 있다는 점이고, 그 과정에서 방문했던 도시들을

비트마스크로 나타낼 수 있다는 점이었다. 

TSP 라는 개념 자체가 중요하고, 이 문제는 다시 풀어볼 가치가 있는 것 같다.

<정답 코드>

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int v[17][17];
int D[17][1 << 16];
int n;
const int INF = 987654321;
int go(int s, int visited)
{
    if (visited == ((1 << n) - 1))
    {
        if (v[s][0] != 0)
        {
            return v[s][0];
        }
        else
        {
            return INF;
        }
    }
 
    if (D[s][visited] != INF)
    {
        return D[s][visited];
    }
 
    for (int i = 0; i < n; i++)
    {
        if (!(visited & (1 << i)) && v[s][i] != 0)
        {
            D[s][visited] = min(D[s][visited], v[s][i] + go(i, visited | (1 << i)));
        }
    }
 
    return D[s][visited];
 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    //freopen("input.txt", "r", stdin);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> v[i][j];
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= (1 << 16) - 1; j++)
        {
            D[i][j] = INF;
        }
    }
 
    cout << go(0, 1) << endl;
 
    return 0;
}