백준 - 2098번 외판원 순회

문제

도시들을 한 번만 들리면서 출발 도시로 돌아오는 순회 여행 경로 계획
외판원 순회 문제

생각

1->2-> ...
1->3-> ...
1->4-> ...

이런 식으로 모든 경우를 다 해봐야 알 것 같은데
그냥 다 봐주면 16!으로 시간초과가 난다
(16!은 생각 외로 엄청 크더라..! 13!이 60억이던데?ㅋㅋㅋ)

DP

그러니까 dp를 써주자! 어떨때?
1->2->3->4
1->3->2->4
이런 경우 그 다음에 해봐야하는 경우가 같으니까

dp[현재위치][방문한도시들정보]에 비용의 합의 최소 값을 저장해놓고 다니자!
그럼 어디 위치까지 어느 상태로 최소로 오는 법을 구해놓고
다음에 또 필요하면 그냥 꺼내쓰면 되는 것! 좋구만~~

비트마스킹

방문한 도시들 정보를 빠르고 간단하게 쓰기 위해서 비트마스킹을 써준다

000...000 으로 초기화 해주고
1번째 도시에 가면 000..001 표시!
2번째 도시에 가면 000..011 표시하는 식으로,

현재 상태에서 i번째 도시가 가봤던 도시인지 비교는
if(state & (1 << i))

새로 i번째 도시에 갈 때 상태 업데이트는
state | (1 << i)

모든 도시를 다 돈 상태인지 확인할 때는
if(state == (1 << n) - 1) 이런식으로 비트마스킹 사용해주자!

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

const int IMPOSSIBLE = 1234567890;
int n;
int w[20][20];
int dp[16][1 << 16];

int TSP(int now, int state) {
	int &ret = dp[now][state];
	
	//이미 계산했던 적이 있으면
	if (ret != 0) {
		return ret;
	}

	//모든 마을 방문했으면 원점으로 갈 수 있는지 봐야지
	if (state == (1 << n) - 1) {
		if (w[now][0] != 0) {
			return w[now][0];
		}
		else {
			return IMPOSSIBLE;
		}
	}

	ret = IMPOSSIBLE;
	for (int i = 0; i < n; i++) {
		//방문한 적 있거나 || now->i 로 갈 길이 없거나
		if (state & (1 << i) || w[now][i] == 0) {
			continue;
		}
		ret = min(ret, TSP(i, state | (1 << i)) + w[now][i]);
	}

	return ret;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> w[i][j];
		}
	}

	cout << TSP(0, 1);

	return 0;
}