[알고스팟 - TSP1] Traveling Salesman Problem 1

||문제 이해

각 그래프를 한번씩 방문할 때 최소 거리를 구하여라.

---

||해결 계획

n개의 그래프를 한번씩 순회하는 경우의 수는 n! 이다.

그중 가장 최소거리를 지니는 단 하나의 답을 구하는 최적화 문제이다.

 

다른 방법도 있지만 가장 기초적인 방법 완전 탐색이 있겠다.

---

||계획 검증

문제에서 그래프의 최대 개수는 8개이다.

그럼 재귀를 8!번 실행해야 하는데

 

8! = 40320 이므로 O(40320)으로 충분히 실행할 수 있다.

---

||오답 원인

초기화 해야할 변수는 초기화 하지 않고

초기화를 안해도 되는 변수는 초기화를 해버려서 오답처리를 두번 당했다ㅠ

 

조심좀 하자ㅠ

---

||구현

#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;

int C, N;
double ret;
bool check[10];
double m[10][10];

//idx : 현재 있는 나라
//temp : 중간 결과 값
//cnt : 방문한 나라, 처음에 1을 넣어 시작한다.
void Count(int idx, double temp, int cnt)
{
	//기저 사례
	if (cnt == N)
	{
		ret = min(ret, temp);
		return;
	}
	
	//1.방문하지 않은 나라를 모두 탐색
	check[idx] = true;
	for (int i = 0; i < N; ++i)
	{
		//1-1. 방문하지 않은 나라여야하고, 현재나라가 아니어야한다.
		if (check[i] == false && i != idx)
		{
			check[i] = true;
			Count(i, temp + m[idx][i], cnt + 1);
			check[i] = false;
		}
	}
	check[idx] = false;
}

int main()
{
	cout << fixed << setprecision(10);
	cin >> C;
	while (C--)
	{
		//1. input,init value
		cin >> N;
		ret = 1.7976931348623158e+308;
		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < N; ++j)
			{
				cin >> m[i][j];
			}
		}

		//2. Calculate
		for (int i = 0; i < N; ++i)
		{
			Count(i, 0.0, 1);
		}
		cout << ret << endl;
	}
	return 0;
}

---

||되돌아보기

이번에 좀 다시 짚고 넘어가야한건 output formating이다.

분명 double을 사용했는데 알아서 반올림이 되어 출력이 되었다.

맨 마지막 출력에 디버깅 창과 다르게 반올림이 되어 출력 된다.

그래서 생각난게 output formating인데 오래전에 공부해서 기억이 잘 안나 찾아봤다 =~=;

 

fixed가 있는 setprecision은 소수부 기준으로 몇자리까지 보여줄 것인가를 의미하기 때문에 사용하였고

한번만 사용해주어도 뒤에 계속 유지되기에 앞에 사용했다.