외판원 순회

문제 링크

사실 할 일 정하기 문제와 거의 똑같고 비용 계산하는 디테일만 조금 다르다. 특히 발상 자체가 완전히 똑같기 때문에 문제를 먼저 푸는 것을 추천한다.

발상

최소비용으로 모든 도시를 방문하는 루프를 찾는 문제다. 도시 어디에서든 출발할 수 있지만 어느 도시에서 출발하든 이 루프를 찾을 수 있으므로 편의상 1번 도시에서 출발해 탐색하기로 한다. 이전 문제와 마찬가지로 현재 도시와 방문한 도시 목록이 정해지면 나머지 경로의 최소 비용도 확정된다. 따라서 현재 도시와 방문한 도시를 인자로 점화식을 세울 수 있다.

점화식

$$\{\begin{array}{l}{n}_{i,j}=\text{i번째 도시에 j 방문 상태로 체류 중일 때 나머지 도시를 방문하는 최소비용}\\ a_{i,j}=\text{i번째 도시에서 j번째 도시로 가는 비용}\end{array}$$ $$n_{i,j}=\underset{k=1\to n}{\min }(n_{k,j\oplus 2^{k-1}}+a_{i,k})$$

점화식은 이전 문제와 사실상 같다보면 된다. 단, 실제 코드를 짤 때는 해당 도시 방문 가능 여부를 별도 확인해줘야 한다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector<vector<int>> arr, dp;
int r(int x, int st) {
	if (dp[x][st] != -1) return dp[x][st];
	if (st == ((1 << n) - 1)) { // 모든 도시를 방문한 경우
		// 1번 도시로 돌아가는 길이 없으면 에러 값(21e8), 있으면 비용 리턴
		return dp[x][st] = (arr[x][1] == 0 ? 21e8 : arr[x][1]);
	}
	int mn = 21e8;
	for (int i = 2; i <= n; i++) {
		if (arr[x][i] == 0) continue; // 방문할 수 없는 도시면 탐색 생략
		if ((st & (1 << (i - 1))) == 0) {
			int s = r(i, st | (1 << (i - 1))) + arr[x][i];
			mn = mn < s ? mn : s;
		}
	}
	return dp[x][st] = mn;
}
int main()
{
	cin >> n; arr = vector<vector<int>>(n + 1, vector<int>(n + 1)); dp = vector<vector<int>>(n + 1, vector<int>(1 << n, -1));
	for (int i = 1; i <= n; i++) {		
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
		}
	}
	cout << r(1, 1);
	return 0;
}