가장 기초적인 비트마스크 DP 문제.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

/*

1. 노드가 N개인 양방향 그래프에서 어느 한 노드를 출발해 모든 노드를 방문하고 시작점으로
   돌아오는 순회 경로를 만든다고 할 때(단, 한번 지난 노드는 다시 지날 수 없다),
   지나온 간선 가중치의 합이 최소인 경로의 가중치의 합을 구하는 문제.
   
   
2. dp[mask][i]: mask라는 경로를 거쳐 i번 노드에 도착했다 할 때,
                거기서 추가로 그래프를 순회해 하나의 순회경로를 완성했을 때
                i번 노드에서부터 추가로 지나가야 하는 간선 가중치 합의 최솟값
                
   으로 dp 배열을 정의한 후, 다음과 같은 점화식을 통해 DP 문제로 풀 수 있다.

   dp[mask][i] = min( dp[(mask에서 j를 추가로 방문)][j] + W[i][j] );

   DFS에 DP가 결합된 것 같은 구조를 가지고 있다. dp[mask][i] 값은 DFS를 통해 하위 단계인
   dp[mask...j][j] 값이 구해진 후에야 비로소 채워진다. 다만, 한번 dp[mask][i]값이 채워졌다면
   또 다시 거기서 dp[mask...j][j]값을 구하러 탐방하지 않고 곧바로 dp[mask][i]값을 리턴하면 되므로
   기존 DFS로 구현하는 것에 비하면 많은 경우의 수가 단축되게 된다. (이를 memoization이라 한다.)
   하위단계의 dp[mask...j][j]값을 구할 때에는, 어떤 경로로 mask값이 만들어졌건
   그 상위단계의 경로와 하위단계가 서로 완전히 독립적이며 따라서 이전의 탐색에서 만들어진 
   dp[mask...j][j]값을 그대로 사용하여도 무방한 것이다. 그래서 이런 관점에서 문제를 접근하는 
   것이 가능하다.


3. DP 문제를 풀 때 가장 중요한 것은 구체적 점화식을 세우는 것인데, 그에 못지않게 중요한 것이
   dp 배열의 정의를 구하는 것이다. dp 배열의 정의를 구하는 과정은 이 문제가 DP로 어떻게 풀리는지,
   정확히는 dp[i][j]의 i와 j를 무엇으로 정의해야 현재 단계와 하위 단계를 서로 완전히 독립적으로
   구분할 수 있는지를 알아내는 과정이다. dp[i][j]를 잘못 정의하면 dp[i][j]를 구하기 위해
   아직 미처 제대로 구해지지 않은 상위단계의 dp값을 참조하는 점화식을 세우게 되는 일이 발생할
   수도 있다. 뒤에서 구해진 값이 달라진다고 하위단계에서 미리 구해놓은 값이 이에 영향을 받는 경우도
   dp 배열을 잘못 정의한 경우다. dp 배열을 정확히 정의하면, 하위 단계에서 미리 구해놓은 dp값을
   단 한 번의 호출로 상위단계에서 그대로 활용하여 단시간 내에 전체적인 dp 배열의 값이 채워지도록
   구현을 할 수 있다.
*/


#include <iostream>
#include <vector>

using namespace std;
const int INF = 20000000;
int N;
vector<vector<int>> dp, W(16, vector<int>(16, 0)); 

bool is_visit(int mask, int j)
{
    return (mask & (1<<j)) != 0;
}

int get_dp(int mask, int i)
{
    if (mask == (1 << N) - 1)
        return W[i][0];
    else if (dp[mask][i] == INF)
        for (int j = 0; j < N; j++)
            if (is_visit(mask, j) == false && W[i][j] != INF)
                dp[mask][i] = min(dp[mask][i], get_dp(mask | (1 << j), j) + W[i][j]);
    return dp[mask][i];
}

int main()
{
    cin >> N;
    for (int i=0; i<(1<<N); i++)
        dp.push_back(vector<int>(N, INF));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            cin >> W[i][j];
            W[i][j] = (i==j || W[i][j] != 0) ? W[i][j] : INF;
        }
        
    cout << get_dp(1 << 0, 0);
    return 0;
}