외판원 순회 2098번 [백준]

외판원 순회 2098번

이번에 풀은 문제는 외판원 순회 TSP(Traveling Salesman Problem)입니다.

문제는 외판원이 외부의 지역들을 순회하면서 물건을 팔고 다시 집으로 돌아오는 것과 같이. 

각 노드을 최소비용으로 한번씩만 순회하여 돌아오는 거리의 합을 구하는 것입니다.

 

먼저 문제을 풀기전에 전체 탐색으로 구해 보았는데요. 

아래와 같이 Bitmask을 사용하여 방문한 노드를 인식함으로써 탐색할 수 있었습니다. 하지만 이렇게 풀게 되면 시간초과가 나게 될것입니다.

int n, ans = inf;
int path[17][17];
void find_path(int start, int end, int cur_path_distance, int visited) {
	int all_visited = (1 << n) - 1;
	
	if (visited == all_visited && path[end][start]) {
		ans = min(ans, cur_path_distance + path[end][start]);
	
		return;
	}

	rep(i, n) {
		if (!path[end][i + 1] || (visited & 1<<i)) continue;
		find_path(start, i + 1, cur_path_distance + path[end][i + 1], (visited|1<<i));
	}
}

void solve() {
	cin >> n;
	rep(i, n) {//rep(i,n) = for(ll i = 0;i<n;i++)
		rep(j, n) {
			cin >> path[i + 1][j + 1];
		}
	}

	find_path(1, 1, 0, 1);
	
	cout << ans << endl;
}

 

따라서 DP을 사용하였습니다. DP을 사용하기 위해서는 먼저 중복되어서 탐색하는 경우를 제외 시켜야 하는 경우를 찾아야 합니다.

이문제의 경우 전체탐색에서 Stack(recursive)을 사용하여 문제을 풀었으므로  TOP => DOWN형태로 중복되는 경우를 제외을 시키도록 하였습니다. 

경로는 신경을 쓰지 않아도 되므로, cache배열을 사용하여 현재 end번째 노드에 도달이 되어있고 방문한 노드을 중심으로 최솟값을 구하였다면 제외시키도록 하였습니다.

ll n;
ll path[17][17];
vector<vector<ll>> dp;
ll find_path(ll end, ll visited) {
	ll all_visited = (1 << n) - 1;
	if (visited == all_visited && path[end][1]) {
		return path[end][1];
	}
	if (dp[end][visited] != -1) {
		return dp[end][visited];
	}
	ll tmp = inf;
	rep(next, n) {
		if (!path[end][next + 1] || (visited & (1 << next)))continue;//path가 0 이거나 이미 방문을 한 곳이라면 skip을 한다. 
		tmp = min(tmp, find_path(next+1, (visited | (1 << next))) + path[end][next+1]);
	}
	dp[end][visited] = tmp;
	return tmp;
}

void solve() {
	dp = vector<vector<ll>>(17, vector<ll>(65537, -1));	
	cin >> n;
	rep(i, n) {//rep(i,n) = for(ll i = 0; i<n;i++)
		rep(j, n) {
			cin >> path[i + 1][j + 1];
		}
	}
	cout<<find_path(1,1);
}

감사합니다.

https://www.acmicpc.net/problem/2098