비트마스크+DFS (BOJ 2098)

문제

외판원 순회(BOJ 2098)

주요 요소

DP[N][1<<N] : 경로별 최소합, 이동 경로는 비트마스크로 표시, 방문하지 않은 지점은 0으로 초기화
weight[N][N]: vertex1->vertex2로 이동하는 비용

알고리즘

1. DP[vertex][mask]를 inf로 초기화
2. 모든 vertex를 방문할 때까지 DFS로 탐색을 반복 (mask = 11..1)
3. 마지막 vertex에서 이동 비용(weight[vertex1][vertex2])을 더해주며 리턴, 이를 최초 지점까지 반복
4. 모든 경로(mask)를 탐색해 이동 비용의 합이 가장 낮은 값을 DP[vertex][mask]에 저장

코드

#include <bits/stdc++.h>

using namespace std;
const int inf = 0x3f3f3f3f;
int DP[16][1<<16], weight[16][16], N;

void input(){
    cin >> N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            int w;
            cin >> w;

            weight[i][j] = w;
        }
    }
}

int TSP(int vertex, int mask){
    if(DP[vertex][mask]){
        return DP[vertex][mask];
    }

    if(mask == (1<<N) - 1){
        return DP[vertex][mask] = (weight[vertex][0] ? weight[vertex][0] : inf);
    }

    DP[vertex][mask] = inf;

    for(int i=0; i<N; i++){
        if((mask & (1<<i)) || !weight[vertex][i]){
            continue;
        }

        DP[vertex][mask] = min(DP[vertex][mask], TSP(i, mask | (1<<i))+weight[vertex][i]);
    }

    return DP[vertex][mask];
}


int main(){
    input();
    cout << TSP(0, 1);

    return 0;
}