BOJ 2098 - 외판원 순회 TSP

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

2098번: 외판원 순회

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 1e9;

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

int TSP(int curr, int visited) {
	//모든 마을을 방문함
	if (visited == (1 << n) - 1) {
		if (w[curr][0] != 0) return w[curr][0];  //마지막 정점~시작점 경로를 더해줘야 한다
		return INF;
	}

	int& ret = dp[curr][visited];
	if (ret != -1) return ret;

	ret = INF;
	for (int next = 0; next< n; next++) {
		//i번 마을을 이미 방문했거나 i번 마을로 갈 수 없음
		if (visited & (1 << next) || w[curr][next] == 0) continue;
		ret = min(ret, TSP(next, visited | (1 << next)) + w[curr][next]);
	}
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &w[i][j]);
	memset(dp, -1, sizeof(dp));
	printf("%d\n", TSP(0, 1));
}

tsp(한 정점에서 나머지 모든 정점을 방문하고 다시 돌아오는 문제) 경로중 가장 적은 비용을 출력하는 문제이다.

 

라이님 블로그(https://blog.naver.com/kks227)에서 알려준 방법을 리뷰.

 

tsp(curr, visited) 는 현재 방문한 정점이 curr이고 여태 방문한 정점들의 집합이 visited일때 tsp경로의 최소값을 반환한다.

 

이 떄 정점의 최대값이 16이므로 bitmask를 이용하면 visited집합을 int형 변수로 표현할 수 있다.

->tsp문제중 n이 아주 작을 떄만 사용 가능한 방법이라고 한다.

 

최악의 경우 그래프가 완전그래프 형태이다. 완전그래프라고 생각하면 시간복잡도를 파악하기가 쉽다. dfs로 완전탐색을 한다면 모든 경우를 다 헤아려야 하므로 O(n^n)쯤으로 시간초과가 뜬다. (방문했던 정점을 다시 방문해도 됨)

 

이때 dp를 이용한다면 시간복잡도는 방문하는 정점의 수 n * (부분문제의 시간복잡도) = O(n^2*2^n)이다.