BOJ 백준 2098 : 외판원 순회

시작하면서

　이번 문제는 다이나믹 프로그래밍(Dynamic Programming)과 비트마스킹(Bitmasking)을 혼합한 문제이다.

BOJ 2098 - 외판원 순회

​

문제 이해

​ 외판원 순회 문제는 TSP(Traveling Salesperson Problem)이라고 불리우며 정형화된 문제 중 하나이다. 아래 링크에서 방법을 확인한 후에 문제를 푸는 것을 추천한다. (그림 그리면서 설명할 자신이 없음…)

LINK

​

해결

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

#define MAX_INT (1987654321)

int recursive(vector<vector<int> >& dp, vector<vector<int> >& weight, int current, int visitedMask)
{
    int size = weight.size();

    if (visitedMask == (1 << size) - 1)
    {
        if (weight[current][0] == 0)
        {
            return MAX_INT;
        }
        else
        {
            return weight[current][0];
        }
    }

    if (dp[current][visitedMask] != -1)
    {
        return dp[current][visitedMask];
    }

    dp[current][visitedMask] = MAX_INT;

    for (int i = 0; i < size; i++)
    {
        if (weight[current][i] == 0)
        {
            continue;
        }

        if (visitedMask & (1 << i))
        {
            continue;
        }

        dp[current][visitedMask] = min(dp[current][visitedMask], weight[current][i] + recursive(dp, weight, i, visitedMask | (1 << i)));
    }

    return dp[current][visitedMask];
}

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off

    vector<vector<int> > dp;
    vector<vector<int> > weight;
    int n;

    cin >> n;

    dp.resize(n);
    weight.resize(n);
    for (int i = 0; i < n; i++)
    {
        dp[i].assign(1 << n, -1);
        weight[i].resize(n);
        for (int j = 0; j < n; j++)
        {
            cin >> weight[i][j];
        }
    }

    cout << recursive(dp, weight, 0, 1);

    return 0;
}