백준 10971번 외판원 순회 2 문제풀이(C++)

백준 10971번 외판원 순회 2

아이디어

어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다

N과 M (1) 문제에 썼던 백트래킹 알고리즘을 이용했다.

i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0

W[i][j] == 0 일 때, 예외처리

가장 적은 비용

문제풀이

#include<bits/stdc++.h>
using namespace std;
int n;
int W[12][12];
bool visited[12];
int ans = 987654321;
void backTracking(int cur, int idx, int sum, int cnt) {
	if (ans <= sum)return;
	if (cnt >= n) {
		if (W[idx][cur])
			ans = min(ans, sum + W[idx][cur]);
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			if (!W[idx][i])continue;
			visited[i] = true;
			backTracking(cur, i, sum + W[idx][i], cnt + 1);
			visited[i] = false;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> W[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		visited[i] = true;
		backTracking(i, i, 0, 1);
		visited[i] = false;
	}
	cout << ans << '\n';
	return 0;
}