백준 10971. 외판원 순회2

알고리즘 기초 문제 중 브루트포스-순열 문제(520)

외판원 순회2

1. 간단 설명

외판원 순회 문제(Traveling Salesman Problem) 중, 브르투포스로 해결 가능한 범위의 문제

직접 계산하면서 최소값을 구하면 된다

주의사항

• 한번 방문한 도시는 다시 갈 수 없음
• 도시간 이동 비용은 대칭적이지 않음
• 도시간 이동이 불가능한 경우도 있음
• N개의 도시를 모두 거쳐서 다시 원래의 도시로 돌아와야한다

2. 예시

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

의 경우

2 -> 0 -> 1 -> 3 -> 2 순으로 순회할 경우

비용이 6 + 10 + 10 + 9 = 35로 최소값이 된다

3. 알고리즘

완전 탐색을 이용하여 모든 도시를 방문 후 돌아왔을 때 최소값을 확인하고, 기록된 값과 비교한다

1. N과 각 도시간의 연결값 W[i][j]를 입력받는다
2. 0번 도시부터 출발하여 각 도시들을 방문한다
	2-1. 도시간 이동하면서 추가된 비용들을 기록해둔다
	2-2. 모든 도시들을 방문한 경우, 다시 출발했던 도시로 돌아온다
	2-3. 이때 마지막으로 이동한 비용도 기록했던 비용에 기록해두고, 이를 최소값과 비교한다
3. 1번 도시부터 N-1번 도시까지 같은 과정을 반복한다
4. 최소값을 출력한다

필요 변수

• 도시 개수 int N (2 ≤ N ≤ 10) 보통 알고리즘 문제는 10개 이하면 완전탐색 가능한듯??
• 도시간 이동 비용 int map[N][N]. 각 행렬의 성분은 100만 ㅇ이하의 양의 정수
• 도시 방문 여부 int visited[N]. 0과 1로만 표시되므로 bool형도 상관없음
• int min_cost 결과를 위한 최소값.
  • 모든 도시 이동 비용이 100만인 경우, 최대 100만 * 10 = 1000만 이므로 int형으로 처리 가능
• 재귀함수 dfs(int start, int now, int level, int cost)
  • int start : 시작한 도시 번호. 이 도시로 돌아와야함
  • int now : 현재 방문중인 도시
  • int level : 몇개의 도시를 방문했는지. level이 N-1이 되면 모든 도시를 방문한 것
  • int cost : 현재까지 누적 비용

4. 소스코드

#include <iostream>

using namespace std;

int N;
int map[11][11];
int visited[11];
int min_cost = 21e8;

// 첫 출발 도시, 현재 도시, 몇번째 경로, 현재까지 비용을 받음
void run(int start, int now, int level, int cost) {
	if (cost > min_cost) return; // 가지치기 : 이미 최소 비용을 초과한 경우 더이상 보지 않음
	if (level == N-1) { // 모든 도시를 방문한 경우
		
		// 집으로 돌아갈 경로가 없다면 리턴
		if (map[now][start] == 0) return;

		cost += map[now][start]; // 마지막으로 원래의 도시까지 돌아오는 코스트 계산

		min_cost = min(min_cost, cost);
		return;
	}

	for (int i = 0; i < N; i++) {
		if (map[now][i] == 0) continue; 
		if (visited[i] == 1) continue;

		visited[i] = 1;
		run(start, i, level + 1, cost + map[now][i]);
		visited[i] = 0;
	}
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	
	for (int i = 0; i < N; i++) {
		visited[i] = 1; 
		run(i, i, 0, 0);
		visited[i] = 0;
	}
	
	cout << min_cost;

	return 0;
}

• next_permutation을 이용한 버전 ```cpp #include #include #include

using namespace std;

int main() {

int N; // 도시 수 
int W[10][10]; // i->j 이동 비용

scanf("%d",&N);

for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		scanf("%d", &W[i][j]);
	}
}

vector<int> d(N); // 도시의 번호가 저장된 배열
for (int i = 0; i < N; i++) {
	d[i] = i; 
}

int ans = 2147483647;

do {
	bool ok = true;
	int sum = 0; 
	for (int i = 0; i < N - 1; i++) {
		if (W[d[i]][d[i + 1]] == 0) { // 이동할 수 없는 경우라면 
			ok = false;
		}
		else {
			sum += W[d[i]][d[i + 1]]; // 비용 계산
		}
	}

	// 마지막 원래도시로 귀환
	if (ok == true && W[d[N - 1]][d[0]] != 0) { 
		sum += W[d[N - 1]][d[0]];
		if(ans> sum) ans = sum;

	}

} while (next_permutation(d.begin() + 1, d.end())); // 1을 시작점으로 고정한 뒤 2,3,...N 의 순열 구하기

printf("%d\n", ans);
return 0; } ```

마지막으로 돌아오는 부분이 햇갈려서 꽤 해멨다

첫 도시를 방문처리하고 들어가느냐, 아니면 마지막에 돌아오면서 방문처리하느냐에 따라 세부적인게 달라짐