알고스팟 Traveling Salesman Problem 1

https://algospot.com/judge/problem/read/TSP1

algospot.com :: TSP1

 

 

 

n의 크기에 따라 풀이법을 달리해야 하는 유명한 문제라고 한다.

이 문제는 n이 8로 매우 작으므로 완전탐색으로 풀 수 있다.(7!)

MST 만들기로도 풀리나??

 

 

---

 

 

<접근방법>

0. 완전탐색 한다.

1. 순열을 만든다.

2. 하나의 경로를 만들면서 최단거리와 현재 경로의 비용을 비교한다.

만약 현재 경로가 최단거리보다 더 크다면 끝까지 볼 필요도 없이 컷트한다.

3. 완전탐색이 끝나면 최솟값 출력.

 

 

 

<시간 복잡도>

순열의 경우의 수 = (n-1)!

 

 

 

<유의할 점>

1. 책에 시작점이 어디든 답은 같다고 했다.

하지만 n이 3일 때 생각해봤는데 다르다.

아마 문제가 다른거 같다.

 

2. 도시를 하나만 선택했을 때는 가중치에 대한 부분은 없어야한다.

이것에 대한 처리가 매끄럽지 않다.

 

3. 현재 경로와 현재의 최단거리를 비교를 하고 선택할지 말지 결정을 하는데

선택이 되든 안되든 현재 경로를 선택한 것으로 갱신을 하게하는 실수를 하였다.

시간이 아깝다.

 

4. scanf, prinf 서식문자 때문에 scanf와 printf를 버리기로 했다.

cin, cout이 더 멋있는거 같기도 하고^^

 

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

 

5.

cout << fixed;

-> 소수점을 고정시켜서 표현하겠다.

cout.precision(10);

-> 10자리까지 표현하겠다.

 

<코드>

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <limits.h>
using namespace std;

int tc, n, pm[9], visit[9];
double map[9][9], res, tres;

void make(int dep = 0) {
	if (dep == n) {
		res = min(res, tres);
		return;
	}

	for (int i = 0; i < n; i++) {
		if (visit[i] == 1) continue;

		if (dep == 0) {
			pm[dep] = i;
			visit[i] = 1;
			make(dep + 1);
			visit[i] = 0;
		}
		else {
			int from = pm[dep - 1];
			int to = i;

			if (tres + map[from][to] > res) continue;

			pm[dep] = i;
			visit[i] = 1;
			tres += map[from][to];
			make(dep + 1);
			visit[i] = 0;
			tres -= map[from][to];
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout << fixed;
	cout.precision(10);

	cin >> tc;

	while (tc--) {
		res = INT_MAX;
		tres = 0;
		memset(visit, 0, sizeof(visit));

		cin >> n;

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

		make();

		cout << res << '\n';
	}
	return 0;
}