백준 10971 외판원 순회2

https://www.acmicpc.net/problem/10971

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 n개의 도시를 입력받고 각각의 도시에서 도시로 이동하는 입력 비용을 입력받은 뒤 모든 도시를 순회하는 가장 작은 비용을 출력하는 문제입니다.

 

visited 배열을 선언해서 각 도시를 방문했는지를 체크하면서  dfs를 이용하면 풀리는 문제입니다. 

 

도시에서 도시로의 비용이 0일때는 이동이 불가능한 것이므로 이동을 못하도록 조건을 넣어주어야 합니다.

 

외판원 순회는 NP-Hard 문제로써 N이 커지면 엄청난 시간이 걸리는 문제입니다. 따라서 dfs를 이용하면 N!의 시간이 걸리게되어 이문제에선 통과하지만 N이 더커지면 불가능하죠.

 

실제로 N이 더커지면(약16정도) 비트마스킹+dp로 푸는 O(2^N*N^2)정도로 해결할 수 있는 방법도 있습니다.

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

int arr[11][11];
int visited[11];
int cost;

int mini = 200000000; //최소 비용 
int first; // 첫번째 방문점 

void tour(int a, int cost, int n, int num) {
	
	if(num == n && arr[a][first] != 0) { //모든 도시를 방문한경우 
		cost += arr[a][first];
		if(mini > cost)
			mini = cost;
		return;
	}
	
	visited[a] = 1;
	
	
	for(int i = 0; i < n; i++) { 
		if(!visited[i] && arr[a][i] != 0) { //방문하지 않은 도시이고 그도시로 가는 비용이 0이 아니라면 방문 
			tour(i, cost + arr[a][i], n, num+1);
			visited[i] = 0;
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n;
	int num;
	cin >> n;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			cin >> arr[i][j];
			
	for(int i = 0; i < n; i++) {
		cost = 0;
		num = 1;
		first = i;
		fill_n(visited, 11, 0);
		tour(i, cost, n, num);
		
	}
	cout<<mini;
	
	return 0;
}