백준 10971 : 외판원 순회 2

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

1. 접근

• 가장 처음으로는 BFS 함수를 이용하여 구현해 보았다..그러나 시간 초과가 발생했다. 아무래도 직접 모든 노드를 돌아다니는 것이 많은 비효율을 가져온 것 같았다.
• 따라서, 굳이 돌아다니지 않고 경로를 미리 짜서 그 값만 확인하는 방식을 생각했다.
• 경로를 미리 짜기 위해서는, 모든 도시가 한번씩 나오면서 한 도시만 두번 나오는 경우를 구해야 했는데, 이전 문제에서 사용했던 순열과 그 의미가 같았다.
  => 순열을 이용하여 미리 경로를 짜고, 그때의 비용만 비교하자!

2. 나의 풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> cities;
int map[11][11];
int n;
int mincost=0;

void TPS() {
	int x, y;
	int cost = 0;
	for (int i = 0; i < cities.size()-1; i++) {
		x = cities[i];
		y = cities[i + 1];
		if (map[x][y] == 0)	return;
		else cost += map[x][y];
	}

	if (map[cities[cities.size() - 1]][cities[0]] != 0)	cost += map[cities[cities.size() - 1]][cities[0]];
	else return;

	mincost = min(mincost, cost);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			mincost += map[i][j]; //주의?
		}
	}

	for (int i = 0; i < n; i++) {
		cities.push_back(i);
	}

	do {
		TPS();
	} while (next_permutation(cities.begin(), cities.end()));

	cout << mincost << "\n";
	return 0;
}