백준 2098 - 외판원 순회(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

유명한 문제인 외판원 순회입니다.

외판원 문제에 대한 설명이 잘나와있습니다. 해당 블로그를 참고해주세요!

https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%B8%ED%8C%90%EC%9B%90-%EC%88%9C%ED%9A%8C-%EB%AC%B8%EC%A0%9C 

[알고리즘] 외판원 순회 문제

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#include <map>
#define LL long long
#define pp pair<int, int>
#define F first
#define S second
#define INF 987654321

using namespace std;

int N, ans_bit;
int cost[17][17];
int dp[17][1 << 16];

int dfs(int node, int bit){
    if(bit == ans_bit){ //전부 순환했을 경우
        if(cost[node][0] == 0) return INF;
        else return cost[node][0];
    }
    if(dp[node][bit] != -1) return dp[node][bit];
    dp[node][bit] = INF;
    for(int i = 0; i < N; i++){
        if(cost[node][i] == 0) continue;
        if((bit & (1 << i)) == (1 << i)) continue;
        dp[node][bit] = min(dp[node][bit], cost[node][i] + dfs(i, bit | 1 << i));
    }
    return dp[node][bit];
}

void solve(){
    memset(dp, -1, sizeof(dp));
    int Cost = dfs(0, 1);
    cout << Cost;
}

int main() {
    cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 0; i < N; i++){
	    for(int j = 0; j < N; j++){
	        cin >> cost[i][j];
	    }
	}
	ans_bit = (1 << N) - 1;
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요