(c++)백준 10971번: 외판원 순회 2

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

10971번: 외판원 순회 2

[풀이]

가능한 모든 경로에 대한 비용들을 비교하여 최솟값을 구하였다.

방문하는 도시의 순서에 따라 최종 비용이 달라지므로 순열을 사용하였다.

마지막으로 방문하는 도시에서 출발한 도시로 갈 수 있는지 확인해줘야 한다.

모든 도시가 출발지점이 될 수 있다.

#include <iostream>
#include <algorithm>//min
using namespace std;

int N;
int Min = 99999999;
int startCity;
int Cost[11][11];
bool visited[11];

//순열 구하기->모든 경우의 경로에 대한 비용 비교
void getCost(int cnt, int curCity, int cost) {
	if (cnt == N) {
		if (Cost[curCity][startCity] != 0) {
			Min = min(Min, cost + Cost[curCity][startCity]);
			return;
		}
	}

	for (int i = 0; i < N; i++) {
		if (Cost[curCity][i] != 0 && visited[i] == false) {
			visited[i] = true;
			getCost(cnt + 1, i, cost + Cost[curCity][i]);
			visited[i] = false;
		}
	}
}

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> Cost[i][j];
		}
	}
	//모든 도시가 출발점이 될 수 있음
	for (int i = 0; i < N; i++) {
		startCity = i;
		visited[i] = true;
		getCost(1, i, 0);
		visited[i] = false;
	}
	cout << Min << endl;
}

int main() {
	solution();
	return 0;
}