[BOJ] 백준 2098번: 외판원 순회

TSP (traveling salesman problem) 로 잘 알려진 외판원 순회문제는 NP-Hard 문제로, 마을의 수 n에 대해 다항식의 형태로 복잡도가 계산될 수 없다.

그래서 N의 개수가 매우 적고, 비트마스크를 사용하여 방문한 마을을 1로 표기하여 001011 처럼 1,2,4 번째 마을을 방문했다를 표현할 수 있다.

TSP는 시작점을 어느 마을로 하든 동일한 값이 나오기 때문에 시작 마을을 인덱스 0으로 편의상 둔다.

if (state == (1 << n) - 1 && map[node][0]) {
		return map[node][0];
}

위의 코드는 모든 n개의 마을을 방문하고 마지막 지점으로부터 시작 마을로 되돌아가는 경우가 있는경우 해당 경로를 반환한다. 이 문제에서는 a마을에서 b마을로 갈 수 없는 경우가 0으로 주어진다.

int& ret = dp[state][node];
if (~ret) return ret;

main에서 dp배열을 -1로 초기화를 하였으므로 ~ret은 -1인경우를 제외하고 참값이 된다. 

(이전에 state와 node 파라미터를 전달받아 함수가 호출되어 값이 구해진 경우)
이를 메모이제이션이라 하며 dp의 꽃이다(?)

for (int i = 0; i < n; i++) {
	if (!(state & (1 << i)) && map[node][i]) {
		ret = min(ret, recv(state + (1 << i), i) + map[node][i]);
	}
}

위 코드는 시프트 연산을 통해 i번째 마을의 방문기록을 체크하고 가는 길이 있는 경우 i번째 마을을 state에 저장하여 진행한다.

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <memory.h>
#include <string>
#include <algorithm>

using namespace std;
typedef long long ll;
int n;
int dp[(1 << 16)][17];// state에서 i번째 마을에 있을 때
int map[17][17];
int recv(int state, int node) {
	if (state == (1 << n) - 1 && map[node][0]) {
		return map[node][0];
	}
	int& ret = dp[state][node];
	if (~ret) return ret;
	ret = 17000001;
	for (int i = 0; i < n; i++) {
		if (!(state & (1 << i)) && map[node][i]) {
			ret = min(ret, recv(state + (1 << i), i) + map[node][i]);
		}
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	cout << recv(1, 0);
}