[백준] 10971 외판원 순회 2 c++

백트래킹 문제였는데

조건을 꼼꼼히 체크를 안해서 틀렸다.

원형으로 도는 것이기 때문에

0->1->2->3 이나  2->3->0->1은 같은 경우여서 무조건 시작을 0(or 아무 시작점)이라고 두면 된다.

그리고 sum에 마지막점과 시작점의 비용도 추가해주어야한다.

또한 마지막점과 시작점이 이어져있는지도 체크해주어야한다.

#include<iostream>
#include<cstring>

using namespace std;

int N;
bool visit[10];
int W[10][10];
int minT = 1e9,sum=0;
int a[10];
int b[10];


void dfs(int n,int depth)
{
	
	
	if (depth == N)
	{
		/*for (int i = 0; i < N; i++)
			cout << a[i] <<"  ";
		cout << endl;*/
		if (W[a[N - 1]][a[0]] == 0)//마지막 도시에 돌아올 수 있을 때만   0이면 못돌아온다.
			return;
		sum += W[a[N - 1]][a[0]];//마지막 도시와 첫 도시의 비용도 추가를 해야한다.
		//cout << W[a[N - 1]][a[0]] << endl;
		//cout << "    " << sum << endl;
		if (sum < minT)
		{
			minT = sum;
			
		}
		sum -= W[a[N - 1]][a[0]];
		return;
	}
	
	

	for (int i = 1; i < N; i++)
	{
		if (!visit[i]&&W[n][i] > 0)
		{
			visit[i] = true;
			sum += W[n][i];
			a[depth] = i;
			b[depth] = W[n][i];
			dfs(i, depth+1);
			sum -= W[n][i];
			visit[i] = false;
		}
	}

}

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> W[i][j];
	//a[0] = 0;
	dfs(0,1);
	cout << minT;

}