[백준 알고리즘] 2098번 외판원 순회 c++

DP와 비트마스킹을 활용한 풀이이다.

처음에 _max값을 INT_MAX를 줬다가 틀렸습니다가 떠서 헤맸다

INT_MAX값이면 DFS의 return 값이 INT_MAX가 나올 수 있으므로 

min값을 구할 때 버퍼오버플로우가 발생하므로 잘못된 결과가 도출된다.

_max값을 적절히 설정하는 것도 중요하다.

 

외판원 순회에선 최소비용이 발생하는 경로를 찾는 것인데

어차피 모든 도시를 방문하기에 시작점이 어디든 상관이 없다.

따라서 0번을 시작점으로 하여 DFS를 돌리고

비트마스크가 모두 1이 됬을 때 방문한 도시에서 0번 도시로 향하는 경로가 있어야 순회가 가능한 경우이다.

 

DFS의 x는 현재 방문한 도시 번호를, visited는 방문했던 도시에 대한 정보를 비트 마스크로 담고있다.

dp배열은 _max값으로 초기화 되어있다. 

DFS에서 dp배열이 _max값이 아니면 이미 구해진 dp값이므로 dp[x][visited]를 반환한다.

for에서 0번도시를 제외한 1~n-1번 도시에 대한 dp값의 최소를 구함으로

최소의 비용이 드는 순회 경로를 구할 수 있다.

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

int n;
int _max = 10000000;
int board[16][16];
vector<vector<int>> dp(16,vector<int>(1<<16, _max));

int DFS(int x, int visited){
	if(visited == (1<<n)-1){
		if(board[x][0] != 0){
			return board[x][0];
		}
		return _max;
	}
	if(dp[x][visited] != _max){
		return dp[x][visited];
	}
	for(int i=1; i<n; i++){
		if(((visited | (1<<i))!= visited) && board[x][i] != 0){
			dp[x][visited] = min(dp[x][visited], DFS(i,visited | (1<<i)) + board[x][i]);		
		}
	}
	
	return dp[x][visited];
}
int main(){
	cin >> n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin >> board[i][j];
		}
	}
	

	cout << DFS(0,1);
	return 0;
}