[알고리즘 문제해결 전략] 여행하는 외판원

문제출처

• [알고리즘 문제해결 전략1] - 6장 완전탐색 예제
• 소스코드는 구현한 함수의 동작 여부를 관찰하기 위해 본인의 테스트 코드를 추가하여 작성한 결과이다.

문제 설명

• n(2이상 10이하)개의 도시가 주어지고, 영업 사원은 한 도시에서 출발해 모든 도시들을 방문하고 다시 돌아온다.
• 가장 짧은 경로를 구한다.

문제 접근 방향 (bokyoung)

• 시작점으로 돌아와야 한다.. -> 모든 도시를 하나의 경로로 묶을 수 있어야 한다.
• 그 경로가 최소이면 된다.
• 시작 노드를 고정하고, 다른 노드를 방문하며 거리를 계산한다.
• 모든 노드를 방문했으면 계산한 경로의 거리를 이전 경로의 거리와 비교한 후 작은 경로를 선택한다.

문제 접근 방향 (Solution)

• 각 도시들은 모두 서로 직선으로 연결되어 있다.
• 완전 탐색으로 문제를 풀기 위한 첫 번째 단계는 시간 안에 답을 구할 수 있는지 확인하는 것이다.
• 시작한 도시로 돌아오는 경로를 찾기 때문에, 경로의 시작점은 중요하지 않다. (하나로 고정할 수 있다.)
• 남은 도시들(n-1개)을 나열하는 방법은 (n-1)!가지로 최대 9!=362,880개의 경로가 가능하다.
• 컴퓨터가 1초 안에 처리할 수 있는 양이다.
• 재귀호출을 통해 n개의 도시로 구성된 경로를 n개의 조각으로 나누어 앞에서부터 도시를 하나씩 추가한다.

구현 결과

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;

#define MAX 10

int cnt = 0; // 가능한 경로의 수
int n; // 도시의 수
double dist[MAX][MAX]; // 두 도시 간의 거리를 저장하는 배열
// path: 지금까지 만든 경로
// visited: 각 도시의 방문 여부
// currentLength: 지금까지 만든 경로의 길이
// 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
double shortestPath(vector<int>& path, vector<bool>& visited, double currentLength)
{
	// 기저 사례: 모든 도시를 방문하면 시작 도시로 돌아가고 종료한다.
	if (path.size() == n)
	{
		cnt++;
		cout << "# " << cnt << ": ";
		for (auto ele : path)
			cout << ele << " ";
		cout << endl;

		return currentLength + dist[path[0]][path.back()]; // 시작 도시와 마지막 도시 간의 길이
	}
	double ret = LLONG_MAX; // 매우 큰 값으로 초기화
	// 다음 방문할 도시를 전부 시도
	for (int next = 0; next < n; next++)
	{
		if (visited[next]) continue;
		int here = path.back();
		path.push_back(next);
		visited[next] = true;
		// 나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다.
		double cand = shortestPath(path, visited, currentLength + dist[here][next]);
		ret = min(ret, cand);
		visited[next] = false;
		path.pop_back();
	}
	return ret;
}

int main()
{
	cin >> n;
	// 랜덤으로 dist 형성하기
	for (int r = 0; r < n; r++)
	{
		for (int c = 0; c < n; c++)
		{
			if (r == c) dist[r][c] = 0; // 같은 도시인 경우
			srand((unsigned int)time(NULL)); // srand에 입력되는 seed 값에 따라 rand() 함수의 결과가 달라짐
			int diff = rand() % 9; // 도시 간 길이는 10이하 자연수라고 가정
			if (diff == 0) // 도시 간 길이는 0보다 커야하므로 1로 설정
				diff++;
			dist[r][c] = diff;
		}
	}

	vector<int> path;
	vector<bool> visited(n);
	path.push_back(0);
	visited[0] = true;
	int ans = shortestPath(path, visited, 0);

	cout << ans << endl;
	return 0;
}

Test Case

5