BOJ : 2098 외판원 순회

---

[BOJ 2098(G1)리뷰]

컴퓨터 분야에서 TSP 라고 불리는 굉장히 유명한 문제라고 한다. 한 도시에서 출발하여 N개의 도시를 모두 방문하였을 때 최소비용을 구해야 한다. 처음에 그냥 간단한 최소 스패닝 트리를 구성하는 문제거나, 최단거리를 구하는 문제인 줄 알았는데 모든 도시를 방문해야 하며(방문이 가능할 경우) 다시 도착점으로 돌아와야 한다는 등의 조건때문에 결국 완전탐색을 해야 한다.

하지만 이 문제의 N의 최대값은 16이므로 완전탐색으로 구현하게 되면 16!이라는 어마어마한 시간복잡도를 가지게 된다. 따라서 다이나믹 프로그래밍을 이용하여 시간효율을 증가시켜야 한다.

그리고 이 때, DP를 효율적으로 사용하기 위하여 비트마스킹 이라는 개념을 사용한다. 나도 이 문제에서 처음사용해봤는데 굉장히 신기하고 재밌었다.

각각의 도시에 도착할때마다, 자신이 그동안 방문해왔던 도시도 함께 기록하는것이다. 그러나 이 경우를 일일히 배열을 통해 관리한다면 어마어마한 메모리가 들테지만, 비트마스킹을 이용하면 정수 값 하나로 거쳐온 도시를 체크할 수 있다.

예를들어, visit = 3 이라면 이는 이진수로 "0011"이라는 값을 갖는다. 그리고 오른쪽부터 0번 도시를 가르켜 0번도시와 1번도시를 방문했다는 의미를 가진다.

방문을 체크하는 방법은 현재 visit값에 방문처리하고자 하는 도시를 n이라 했을때 visit ^ (1<<n)해주면 된다. 이게 가지는 의미는 방문처리하고자 하는 비트만 1로 설정하여 or연산을 해주면, 나머지 비트들은 기존의 상태를 유지하고, 방문처리하고자 하는 비트의 값만 변경할 수 있다.

또 방문을 확인하는 방법은 visit & (1<<n)이라 해주면된다. 이 역시 방문을 확인하고자 하는 비트만 1로 설정을 해준 후 기존값과 and연산을 하여 기존에 1로 체크되어있을 때만 1을 반환하게 된다.

위 비트마스킹 기법을 사용하여 dp배열을 채우면 된다. 나는 재귀를 이용한 top-down방식으로 구현을 했다.
dp[cur][visit]은 현재 cur의 도시에 방문했고, visit의 방문정보를 가지고 있을때의 최소값이다. 각각의 도시마다 이동할 수 있는 도시에대하여 함수를 호출하여 최소값을 갱신해주면 된다.

모든 도시를 방문했는지 확인하는 방법은 (visit + 1) == (1<<n)이다. (n은 도시의 갯수)
왜냐면, 만약 모든곳을 방문했다면 모든 비트가 1로 셋팅이 되어있을것이고, 만약 도시의 개수가 4개라면 "1111"이고 이는 15라는 값이므로 (15 + 1 == 2^4) 를 확인해주면 되는것이다.

/*
	21.01.22
	BOJ : 2098 외판원 순회 (https://www.acmicpc.net/problem/2098)
	동적계획법, 비트마스킹
*/
#include <bits/stdc++.h>
using namespace std;

int n;
int dp[16][1 << 16];
int w[17][17];

int setMask(int cur,int n) {
	cur = cur ^ (1 << n);
	return cur;
}

bool isTravle(int visit,int cur) {
	return visit & 1 << cur;
}

long long int travel(int cur, int visit) {
	//방문할 수 있는곳에 대해서 방문한 값중 최소값 저장.
	//기저조건 -> 모든 곳을 방문하고 이곳에 도착했을때. visit == (1<<n)-1 일 때
	//다음 방문할곳을 방문체크하고, 방문
	//방문은 현재 있는곳에서 갈 수 있는곳 모두(방문한 적 없고, 거리가 0 이상이여야 갈 수 있음)

	visit = setMask(visit, cur);
	if (dp[cur][visit] != -1) {
		return dp[cur][visit];
	}

	if (visit + 1 == (1 << n)) { //모든 곳 방문
		if (w[cur][0] == 0) return INT_MAX; //실수한 부분. 마지막 방문 지점에서 시작점으로 돌아갈 수 있는지 확인.
		else return w[cur][0];
	}

	long long int minValue = INT_MAX; //long long int안하면 오버플러우난다. 방문할 수 있는곳이 없는경우 int_max 반환하므로..
	for (int i = 0; i < n; i++) {
		if (w[cur][i] == 0) continue;
		if (isTravle(visit, i) == 1) continue;
		minValue = min(minValue, travel(i, visit) + w[cur][i]);
	}
	
	return dp[cur][visit] = minValue;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	memset(dp, 0xff, sizeof(dp));

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

	cout << travel(0, 0);

	return 0;
}