[Algorithm] Traveling Salesman Problem 1 (Algospot – TSP1)

출처

• https://algospot.com/judge/problem/read/TSP1
• 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 (구종만)

난이도 

• (하) – 중 – 상 – 최상 – 풀지 못함

문제 

• Input으로 최대 8개 도시간의 거리가 주어진다. Salesman이 모든 도시를 한 번씩 다 방문하는데 가장 짧은 거리를 계산하는 문제이다.

후기 

• 문제를 읽고 Priority Queue로 문제를 풀려고 먼저 생각해보았다. 하지만, 도시의 개수가 8개 정도로 제한이 되어 있어서 단순히 모든 가능한 방법을 다 만들어 보는 완전 탐색 방법을 사용하였다. 추가로 가지치기 (Pruning)이라는 기법에 대해서 읽었던 기억이 나서 같이 적용하면 문제를 한번 풀어보았다.
• 완전 탐색 방법과 가지치기를 사용하여 문제를 정말 쉽게 풀었다. 한번 실수를 했던 부분은 Float로 연산을 수행하니 소수점 7자리에서 오차가 조금씩 발생하여 Double로 연산을 하도록 변경하였다.

코드

• 완전 탐색 + 가지치기 방법을 사용한 코드
• Github 주소: https://github.com/mkblog-cokr/algorithmCode
• 실행 시간: 8ms (제일 빠른 코드 대비 8배(1ms) 느림)

//MK: 완전 탐색 + 가지치기 방법을 사용한 코드
#include <stdio.h>

//MK: Visual Studio를 사용시 scanf 에러 제거함.
#pragma warning(disable:4996)

#define MAXSIZE 9
#define MIN(a,b) (a)<(b)?(a):(b)

double distance[MAXSIZE][MAXSIZE];
int inputSize;
double tmpAnswer;
int visited[MAXSIZE];

//MK: 모든 도시를 방문했는지를 판단하는 함수 
int allVisited() {
	for (int i = 0; i <= inputSize; i++) {
		if (visited[i] == 0) {
			return 0;
		}
	}
	return 1;
}

//MK: 모든 가능한 방법을 다 찾기 위한 완전탐색 코드
void findAnswer(int ptr, double dist) {
	if (allVisited() == 1) {
		tmpAnswer = MIN(tmpAnswer, dist);
		//printf("%f\n", dist);
	}
	//MK: 기존의 답 보다 긴 경우 가지치기를 하여서 더 이상 탐색을 수행하지 않음
	if (dist > tmpAnswer) {
		return;
	}
	for (int i = 1; i <= inputSize; i++) {
		if (i == ptr) {
			continue;
		}
		if (visited[i] == 0) {
			visited[i] = 1;
			findAnswer(i, dist + distance[ptr][i]);
			visited[i] = 0;
		}
	}
}

int main(void)
{
	int testCase;
	freopen("input.txt", "r", stdin);
	setbuf(stdout, NULL);
	scanf("%d", &testCase);
	for (int m = 1; m <= testCase; m++)
	{
		for (int i = 0; i < MAXSIZE; i++) {
			visited[i] = 0;
		}
		tmpAnswer = 0;
		scanf("%d", &inputSize);
		for (int i = 0; i <= inputSize; i++) {
			distance[i][0] = 0;
			distance[0][i] = 0;
		}
		for (int i = 1; i <= inputSize; i++) {
			for (int j = 1; j <= inputSize; j++) {
				scanf("%lf", &distance[i][j]);
				if ((i + 1) == j) {
					tmpAnswer += distance[i][j];
				}
			}
		}
		visited[0] = 1;
		findAnswer(0, 0);
		printf("%.10lf\n", tmpAnswer);
	}
	return 0;
}