[BOJ] 2098. 외판원 순회

 

2098번: 외판원 순회

현재까지 방문한 경로를 표현할 때 비트마스크를 이용하는 문제이다.

개인적으로 DP 배열을 현재 경로와 인덱스 두 개의 인자를 써야 한다는 아이디어를 떠올리기가 힘들었다.

#include <iostream>
#include <cmath>

using namespace std;

#define INF 1000000000

int N, W[16][16];
int dp[65536][16];

int func(int route, int index)
{
    int result = INF;
    route |= (1 << index);
    if (dp[route][index])
        return dp[route][index];
    if (route == pow(2, N) - 1)
    {
        if (W[index][0])
            return dp[route][index] = W[index][0];
        else
            return INF;
    }
    for (int i = 0; i < N; i++)
    {
        if ((~(route >> i) & 1) && W[index][i])
        {
            result = min(W[index][i] + func(route, i), result);
        }
    }
    return dp[route][index] = result;
}

int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> W[i][j];
        }
    }
    cout << func(0, 0);
}

 

route는 현재까지 방문한 정점들을 정수로 표현한 것이고, index는 현재 방문 중인 정점이다. 

dp[route][index]에는 현재 route와 index에서 시작 정점인 0으로 가는 최소의 비용이 들어간다.

문제에는 모든 정점에서 출발할 수 있다고 써 있지만, 어차피 시작 정점으로 돌아와야 하기 때문에 사실상 시작 정점은 고정해서 생각해도 무방하다.

기억해둘만한 문제인 것 같다.