여행하는 외판원 문제

여행하는 외판원 문제

 

여행하는 외판원 문제는 유명한 최적화 문제 중 하나다. 최적화 문제는 여러 개의 답 중에서 최소값 또는 최대값을 찾는 문제이기에 완전 탐색 방법으로 풀이 할 수 있다.

다만 도시의 개수가 제한적이라는 조건이 붙는다. 도시의 개수가 매우 크다면 다른 방식으로 풀이해야 한다.

이번 문제는 도시의 개수가 2<=N<=10라고 가정한다.

이렇게 되면 모든 도시를 방문하는 경우의 수는 9!이기 때문에 완전 탐색 방식으로 해결 할 수 있다.

 

풀이 방법

 

지금까지와 마찬가지로 재귀적으로 생각한다.

 

1. 매 호출마다 하나의 도시를 방문해야 한다.
2. 모든 도시를 방문했다면 종료한다.

 

int FindShortestPath(vector<int>& path, vector<bool>& visited, vector<vector<int>>& distances, int currentLength)
{
	// 모든 도시 방문
	if(path.size() == visited.size())
		return currentLength + distances[path[0]][path.back()];

	int ret = INT_MAX;

	for(int next = 0; next < visited.size(); ++next)
	{
		if(visited[next]) continue;

		int here = path.back();
		path.push_back(next);
		visited[next] = true;
		int cand = FindShortestPath(path, visited, distances, currentLength + distances[here][next]);

		ret = min(ret, cand);
		visited[next] = false;
		path.pop_back();
	}

	return ret;
}

int main()
{
	// 도시 개수 입력 받기
	int n;
	scanf("%d", &n);

	// 방문 도시 초기화
	vector<bool> visited(n, false);

	// 0번 도시 방문 시작
	visited[0] = true;
	
	// 도시 간 거리 입력, -1로 초기화
	vector<vector<int>> distances(n, vector<int>(n, -1));

	for(int i = 0; i < n; ++i)
	{
		for(int j = 0; j < n; ++j)
		{
			if(i == j)
			{
				distances[i][j] = 0;
			}
			else if(distances[i][j] == -1)
			{
				distances[i][j] = distances[j][i] = (i+1) + j;
			}
		}
	}

	vector<int> path;
	// 시작 도시 0번
	path.push_back(0);

	cout << FindShortestPath(path, visited, distances, 0) << endl;
	
	return 0;
}

 

회고

 

완전탐색 문제를 많이 풀다보면 비슷한 코드가 작성되어진다는 걸 깨닫는다. 문제를 최대한 단순화시켜서 조각화하여 재귀 함수 호출 내에서 호출될 수 있도록 구현하면 된다.

여기에 문제마다의 기저사례를 발견해서 추가하고 약간의 알고리즘 수정만 해주면 풀 수 있다.

예전에는 완전탐색 문제를 맞닥뜨렸을 때 마다 단순하게

 

반복문 순회하면 되는거 아니야?

생각했던 적도 있었지만... (물론 그렇게도 해결 가능하다)

그렇게 되면 예외처리해야 할 경우도 더 늘어나고 동작도 오히려 더 복잡해진다.