[BOJ] 2098 - 외판원 순회, 16991 - 외판원 순회 3

[백준] 2098 - 외판원 순회

접근

외판원 순회 2문제에서 약간의 응용을 끼얹으면 된다. 완전탐색을 하는 과정에서 메모이제이션을 끼얹으면 된다! 그런데 메모이제이션을 하려고 하니 사소한 문제가 생겼다. 현재 위치는 이전까지 방문했던 도시들에 의해 결정되는데 이것을 어떻게 표시해야 하지? 이 때 사용할 수 있는 것이 바로 비트마스킹이다.
비트마스킹은 각각의 비트를 true, false값을 가지는 불린변수로 바라본다. int형 변수는 32bit이므로, 32개의 bool값을 표시할 수 있는 배열처럼 다룰 수 있는 것이다. 이전까지 도시를 방문했던 순서는 의미를 갖지 않기 때문에 단순히 이전까지 어떤 도시를 방문했는지만 가지고 있으면 된다.

추가 기재사항

1. 처음에는 ‘앗 그럼 2¹⁶만큼의 배열을 만들어야 한단 말이야,,? 너무 큰거 아닌가,,? 하면서 이게 아닐거라 생각했는데 그냥 그만큼의 배열을 만드는 것이 맞았다 겁먹지 말자
2. 비트 연산자를 헷갈려서 굉장히 많은.. 틀렸습니다를 받았다. 우리는 지수표기법을 ^로 쓰지만 컴퓨터는 «로 표현함을 잊지 말도록 하자

소스코드

#include <iostream>
#include <algorithm>
#define INF 987654321
using namespace std;

int dist[15][15], n;
bool visited[15];

int tsp(int now, int cnt) {
	// 다음 도시로 모두 탐색하고 그중 가장 짧은 경로를 선택
	if (cnt == n) {
		return dist[now][1] ? dist[now][1] : INF;
	}
	int rtn = INF;
	visited[now] = true;
	for (int i = 1; i <= n; i++) {
		if (visited[i] || !dist[now][i]) continue;
		rtn = min(rtn, dist[now][i] + tsp(i, cnt + 1));
	}
	visited[now] = false;
	return rtn;
}

int main(void) {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", dist[i] + j);
		}
	}

	printf("%d", tsp(1, 1));
	return 0;
}

[백준] 16991 - 외판원 순회 3
위의 문제에서 거리 구하는 방법만 바뀌었다.

소스코드

#include <iostream>
#include <algorithm>
#include <limits.h>
#include <cmath>
#include <float.h>
#define INF 987654321
using namespace std;
typedef pair<int, int> PII;

double dp[20][(1 << 18) + 1];
int n;
PII point[20];
bool visited[20];

double get_distance(PII x, PII y) {
	return sqrt((double)(x.first - y.first) * (double)(x.first - y.first) + (double)(x.second - y.second) * (x.second - y.second));
}

double tsp(int now, int cnt, int v) {
	// 다음 도시로 모두 탐색하고 그중 가장 짧은 경로를 선택
	if (cnt == n) {
		return get_distance(point[now], point[1]);
	}
	if (dp[now][v]) return dp[now][v];
	double rtn = DBL_MAX;
	visited[now] = true;
	for (int i = 1; i <= n; i++) {
		if (visited[i]) continue;
		rtn = min(rtn, get_distance(point[now], point[i]) + tsp(i, cnt + 1, v | (1 << (i - 1))));
	}
	visited[now] = false;
	return dp[now][v] = rtn;
}

int main(void) {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &point[i].first, &point[i].second);
	}

	printf("%.17lf", tsp(1, 1, 1));
	return 0;
}