백준 10971 외판원 순회 2

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

접근 방식

요새 dfs문제들을 많이 풀어봐서인지 한번에 통과했었다!! 하지만 시간이 맘에 들지 않았다.
대표적인 dfs문제답게 방문하는 배열, 더해주는 값, 횟수 등을 이용해서 푸는건데

처음 접근은 아무 도시에서 출발해서 가장 최소비용으로 돌아다닌 후 다시 출발한 도시로 오는 것 이므로 각 도시마다 dfs를 진행해줘야 한다고 생각했다. 그래서
아래 코드의

dfs(0, 0, 1, 0);

부분이 처음에는

for (int i=0; i<n ; i++) {
    dfs(i,0,1,i); 
}

였었다. 시간이 192ms가 나오길래 응?? 했었다.

다른 사람의 코드를 보면서 나름대로 생각해본 결과

출발 도시 a -> 도시 x -> ••• -> 도시 z -> 출발 도시 a

라는 건 사이클이 만들어진 것이므로 어떤 a에서 출발하던 x에서 출발하던 최솟 비용값은 동일 하다는 것이다!! 만약에 x에서 dfs를 실행했는데 값이 더 작았다면 분명 a에서도 알았을 것이다.
따라서 첫 번째 도시에서만 dfs를 실행하는 코드로 다시 제출했고 시간은 16ms가 나왔다.

코드

#include <cstdio>
int n,minnum = 10000001, W[10][10];
bool visited[10];

int mymin(int a, int b){return a > b ? b : a;}
void dfs(int start,int sum, int times,int end){
	if(times == n){
		if(W[start][end] != 0)
			minnum = mymin(minnum, sum + W[start][end]);
		return ;
	}
	for (int i = 0; i < n; i++){
		visited[start] = true;
		if(visited[i] != true && W[start][i] != 0)
			dfs(i, sum + W[start][i], times + 1, end);
		visited[start] = false;
	}
}
int main(void){
	scanf("%d",&n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &W[i][j]);
	dfs(0, 0, 1, 0);
	printf("%d", minnum);
	return 0;
}