BOJ 2098 외판원 순회

1 개요

BOJ 2098 외판원 순회

• 백준 온라인 저지 2098번 문제
• BOJ 40단계

2 C++

#include <bits/stdc++.h>
using namespace std;

#define INF 1e9
int N;
int W[16][16];
int dp[16][1<<16];

int dfs(int x, int visited) {
    if( visited == (1<<N)-1 ){
        if( W[x][0] == 0 ) return INF;
        return W[x][0];
    }
    if( dp[x][visited] != 0 ) return dp[x][visited];
    int ret = INF;
    for(int i=0; i<N; i++) {
        if( W[x][i] == 0 || (visited & (1<<i)) ) continue;
        ret = min(ret, W[x][i] + dfs(i, visited | (1<<i)));
    }
    dp[x][visited] = ret;
    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> W[i][j];
        }
    }
    cout << dfs(0, 1);
}