풀이

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

#include <iostream>
#include <vector>
#include <unordered_map>

constexpr int INF = 20000000;

using namespace std;

int Solve(
    const int Start, const int CurrentPos, const int VisitBitMask,
    const vector<vector<int>>& Mat,
    vector<vector<vector<int>>>& Table
)
{
    if(Table[Start][CurrentPos][VisitBitMask] > 0)
    {
        return Table[Start][CurrentPos][VisitBitMask];
    }
    else if(VisitBitMask == (1 << Mat.size()) - 1 && Start == CurrentPos)
    {
        return 0;
    }
    else
    {
        int MinCost = INF;
        for(int i = 0; i < Mat[CurrentPos].size(); ++i)
        {
            if(Mat[CurrentPos][i] > 0 && ((1 << i) & VisitBitMask) == 0)
            {
                MinCost = min(MinCost, Mat[CurrentPos][i] + Solve(Start, i, VisitBitMask + (1 << i), Mat, Table));
            }
        }

        return Table[Start][CurrentPos][VisitBitMask] = MinCost;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<vector<int>> Mat(N, vector<int>(N));
    for(vector<int>& Row : Mat)
    {
        for(int& Value : Row)
        {
            cin >> Value;
        }
    }

    vector<vector<vector<int>>> Table(N, vector<vector<int>>(N, vector<int>(1 << N, 0)));   // [Start][CurrentPos][VisitBitMask]: MinCost
    
    int MinCost = INF;
    for(int i = 0; i < N; ++i)
    {
        MinCost = min(MinCost, Solve(i, i, 0, Mat, Table));
    }

    cout << MinCost;

    return 0;
}

1562과 같은 방식으로 접근한 풀이

보는바와 같이 메모리와 시간면에서 성능이 크게 떨어진다.

정답자들의 코드를 분석한 결과, 시작점을 0으로 고정하고 한다.
처음에는 문제 조건 누락이라고 생각했으나, 아래 글을 보고 이해하였다

https://www.acmicpc.net/board/view/148667

최종 풀이

#include <iostream>
#include <vector>

constexpr int INF = 20000000;

using namespace std;

int N;
int Mat[16][16];
int Table[16][1 << 16];

int Solve(const int CurrentPos, const int VisitBitMask)
{
    if(Table[CurrentPos][VisitBitMask] > 0)
    {
        return Table[CurrentPos][VisitBitMask];
    }
    else if(VisitBitMask == (1 << N) - 1)
    {
        return Mat[CurrentPos][0] == 0 ? INF : Mat[CurrentPos][0];
    }
    else
    {
        int MinCost = INF;
        for(int i = 0; i < N; ++i)
        {
            if(Mat[CurrentPos][i] > 0 && ((1 << i) & VisitBitMask) == 0)
            {
                MinCost = min(MinCost, Mat[CurrentPos][i] + Solve(i, VisitBitMask + (1 << i)));
            }
        }

        return Table[CurrentPos][VisitBitMask] = MinCost;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    fill(Table[0], Table[0] + (16 * (1 << 16)), 0);
    
    cout << Solve(0, 1);

    return 0;
}

주요 변경점은 아래와 같다.

1. 시작점을 0으로 고정
2. vector대신 배열을 사용하여 메모리 초기화 시간 단축
3. 시작 비트마스크를 0->1로 변경하여 함수 호출 횟수 감소