백준 10971 (외판원 순회 2)

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

10971번: 외판원 순회 2

 

해당 문제는 N개의 도시가 주어질 때 N개의 도시를 빠짐없이 모두 순회하면서 드는 최소비용을 구하는 문제이다. 이때 도시를 순회하는 과정에 다음과 같은 규칙을 지켜야 한다.

1. 이미 방문한 도시는 재방문 하지 못 한다.

2. 단 마지막 도시에서 가장 처음 도시로 돌아가는 경우에는 재방문이 가능하다.

3. i 번째 도시에서 j 번째 도시로 이동 할 경우에 경로의 값 map[i][j] 이 0인 경우에는 길이 없다고 가정한다.

 

풀이 :

DFS를 사용하여 모든 도시를 방문하는 경우의 수를 탐색하여 그중 최소값을 구하면 된다. 이때 주의해야 할 점은 꼭 n개의 도시를 모두 순회해야 함으로 현재까지 방문한 도시를 계속 cnt 하며 cnt가 n일 경우에만 최소값 경신을 수행한다. 또한 시작위치를 따로 저장해놓은 뒤 마지막 도시에 방문한 뒤 다시 시작 도시로 이동하는 경우를 생각해야 한다. 

#include <iostream>
#include <vector>

using namespace std;

int n, minn = 100000000;
int map[11][11];
int visit[11];

// level == 현재 위치, start == 시작한 도시, cnt == 현재까지 방문한 도시의 수 
void dfs(int level, int sum, int start, int cnt){

	// 도시 n개를 모두 방문해야 함으로 방문한 도시의 수가 n개일 때 최소값 갱신
	if (cnt == n){
		// 첫 방문 도시로 다시 가는 길이 없을 경우 갱신 X
		if (map[level][start] == 0) return;
		// 첫 방문 도시로 다시 가는 길이 있을 경우 비용 추가 후 갱신
		else{
			int resSum = sum + map[level][start];
			if (resSum < minn) minn = resSum;
		}
		return;
	}

	for (int i = 1; i <= n; ++i){
		// 이미 방문한 도시
		if (visit[i] == 1) continue;
		// 길이 없는경우
		if (map[level][i] == 0) continue;
		visit[i] = 1;
		dfs(i, sum + map[level][i], start, cnt + 1);
		visit[i] = 0;
	}

}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n;
	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= n; ++j){
			cin >> map[i][j];
		}
	}

	// 도시 1 번에서 출발 하는 경우부터 N번 에서 출발하는 경우 까지 수행
	for (int i = 1; i <= n; ++i){
		visit[i] = 1;
		dfs(i, 0, i, 1);
		visit[i] = 0;
	}

	cout << minn << endl;
}