백준[C++] 2098 외판원 순회

<조건 분석>

1. 만약 도시를 a -> b -> c -> d -> a 방향으로 방문한다고 했을 때, a->b 의 최소, b->c의 최소 이렇게 부분최적해를 쌓아나가는 문제임.

 

2. 왔던 그 경로를 캐싱으로 저장해놓으면 됨.

 

3. 만약 도시를 방문하는 순서가 중요하다면 N이 최대 16이므로 16! = 20조가 됨. (16개 방문 * 15개 방문 * 14개 방문 ...)

 

4. 순서가 중요하지 않으니 16개의 도시를 집합으로 관리할 수 있게 됨. -> 비트마스킹으로 가능함.

 

<문제 해결 포인트>

 

1. dp의 배열 구조를 [방문한 지점][지금까지 방문한 비트상태] 로 관리함.

 

2. 최소값을 구하는 것 이므로 항상 inf로 설정해놓아야 함. (INT_MAX는 프로그래머스에서 사용 불가)

#include <bits/stdc++.h>
using namespace std;
#define inf 987654321

int N = 0;
int dist[16][16];
int dp[16][1 << 16];
int start = 0;

int TSP(int here, int visited)
{
   if (visited == (1 << N) - 1)
   {
   	return dist[here][start] ? dist[here][start] : inf;
   }
   
   int& ret = dp[here][visited];
   if (ret != -1) return ret;
   ret = inf;
   
   for (int i = 0; i < N; i++)
   {
   	if (visited & (1 << i)) continue;
        if (dist[here][i] == 0) continue;
        
        ret = min(ret, TSP(i, visited | (1 << i)) + dist[here][i]);
    }
    
    return ret;
}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> dist[i][j];
        }
    }

    ::memset(dp, -1, sizeof(dp));

    cout << TSP(start, 1);


    return 0;
}