알고스팟 알고리즘: TSP1(여행하는 외판원 문제, Traveling Salesman Problem) [C++]

문제 출처: https://www.algospot.com/judge/problem/read/TSP1

algospot.com :: TSP1

1. 코드

#include <iostream>

using namespace std;

double dis[8][8];		//도시 사이의 거리
bool check[8];			//이미 지나간 도시
int N;					//도시의 수
double result;			//결과값

//start: 시작하는 도시, cnt: 거쳐간 도시의 수, sum: 지나온 거리
void solution(int start, int cnt, double sum)
{
	if (cnt == N - 1)			//도시를 전부 지났을 때
	{
		if (result > sum)		//기존의 결과값에 비해 지나온 거리가 짧을 때
			result = sum;
		return;
	}

	for (int i = 0; i < N; i++)
	{
		if (start != i && !check[i])
		{
			check[i] = check[start] = true;					//지나온 도시를 생략
			solution(i, cnt + 1, sum + dis[start][i]);
			check[i] = check[start] = false;				//새로운 경로 탐색을 위해
		}
	}
}

int main(void)
{
	//소수점 10자리 출력
	cout << fixed;
	cout.precision(10);

	int C;
	cin >> C;
	
	while (C--)
	{
		cin >> N;

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> dis[i][j];
				result += dis[i][j];
			}
		}
		for (int i = 0; i < N; i++)
			solution(i, 0, 0);
		cout << result << endl;
	}
}

(실행)

2. 풀이

해당 문제는 재귀 함수를 이용해서 쉽게 해결할 수 있다.

//소수점 10자리 출력
cout << fixed;
cout.precision(10);

예제 출력을 보면 소수점이하의 수를 10개가 출력되기 때문에 위 코드를 사용해서 출력 설정을 해준다.

for (int i = 0; i < N; i++)
{
	for (int j = 0; j < N; j++)
	{
		cin >> dis[i][j];
		result += dis[i][j];
	}
}

반복문으로 도시와 도시간의 거리를 이차원 배열을 이용하여 표시해준다. 그리고 result 최종적으로 나오는 결과인데 이 값은 최대한 적어야한다. 근데 도시간의 거리를 입력할 때 그 값을 더해주면 결과가 무조건 이 값보다 클 수없기 때문에 전부 더해준 뒤 이 값을 기준으로 비교해준다.

for (int i = 0; i < N; i++)
	solution(i, 0, 0);
cout << result << endl;

반복문을 이요해서 모든 경우를 비교하게 끔 해준다. 그리고 결과를 출력해주면 된다.

//start: 시작하는 도시, cnt: 거쳐간 도시의 수, sum: 지나온 거리
void solution(int start, int cnt, double sum)
{
	if (cnt == N - 1)			//도시를 전부 지났을 때
	{
		if (result > sum)		//기존의 결과값에 비해 지나온 거리가 짧을 때
			result = sum;
		return;
	}

cnt는 거쳐간 도시의 수인데 한마디로 이동할 떄마다 1씩 증가한다고 생각하면 된다. 그래서 cnt의 값이 N - 1이라면 전부 돌았다는 이야기이기에 이 때 result 값보다 지금까지의 지나온 거리인 sum이 작다면 정답은 sum이기에 result의 값을 sum으로 초기화해주고 해당함수를 종료해준다.

for (int i = 0; i < N; i++)
{
	if (start != i && !check[i])
	{
		check[i] = check[start] = true;					//지나온 도시를 생략
		solution(i, cnt + 1, sum + dis[start][i]);
		check[i] = check[start] = false;				//새로운 경로 탐색을 위해
	}
}

반복문을 통해서 지나가지 않은 도시를 탐색하는데 탐색에 성공하면 check에 지나갔다는 의미로 true를 저장해주고 solution 함수를 실행한다. 그 다음으로 또 다른 경로를 탐색하기 위해 true로 저장했던 것을 false로 저장한다. 이렇게 모든 경로를 탐색할 수 있다.

3. 느낀 점

이전의 문제보다 상당히 쉬운 느낌을 받았다. 비록 재귀 함수를 만들 때 조금 시간이 걸렸지만 익숙해지는 느낌이다.