[백준] 2098번 외판원 순회

[적용한 알고리즘]

DP, 비트마스크

 

[아이디어]

http://kks227.blog.me/220787042377 를 참고했습니다.

비트마스킹(Bit Masking)

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

비트마스킹을 이용한 것은 알겠으나, 코드가 정확하게 와닿지는 않는다. 더 공부해야겠다.

 

<코드>

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int IMPOSSIBLE = 1000000000;

int N, W[16][16], dp[16][1 << 16];

int TSP(int current, int visited){
    //Base Case : 전부 방문한 경우
    if (visited == (1 << N) - 1){
        if (W[current][0] != 0) return W[current][0];
        return IMPOSSIBLE;
    }

    int &ret = dp[current][visited];
    if (ret != -1) return ret;


    ret = IMPOSSIBLE;
    for (int i = 0; i < N; i++){
        if (visited & (1 << i) || W[current][i] == 0) continue;
        ret = min(ret, TSP(i, visited | (1 << i)) + W[current][i]);
    }

    return ret;
}
int main(){
    scanf("%d", &N);
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            scanf("%d", &W[i][j]);
        }
    }

    memset(dp, -1, sizeof(dp));
    printf("%d\n", TSP(0, 1));

    return 0;
}