정올 C++ - 해밀턴 순환회로(1681) DFS, 백트래킹

https://beta.jungol.co.kr/problem/1681?cursor=eyJwcm9ibGVtc2V0Ijo4LCJmaWVsZCI6MiwiaWR4IjoxfQ==

1. 더 이상 탐색하지 않아도 되는 경우를 파악한다.

 1) 이동 비용이 구했던 최솟값(ans)보다 크다면 return

 2) 갔던 장소는 또 다시 가지 않는다.

 

#pragma warning(disable:4996)
#include <stdio.h>
#include<algorithm>
using namespace std;
int graph[15][15], n;
int freq[15], ans = 0x7fffffff;

void dfs(int level, int cost, int cnt) // 장소, 비용, 이동 횟수
{
	if (ans < cost) return; // 비용이 구했던 최솟값보다 크면 리턴

	if (cnt == n) // 회사에 돌아올 차례
	{
		if (graph[level][1] == 0) return; // 회사로 가지 못하면 리턴

		if (ans > cost + graph[level][1]) ans = cost + graph[level][1]; // 최솟값 갱신
		return;
	}
	else // 배달할 장소가 남았다면
	{
		for (int i = 2; i <= n; i++) // 회사는 마지막에 가야하기 때문에 2부터 시작
		{
			if (freq[i] != 1 && graph[level][i] != 0)  // 참조하지 않았고 다음 장소로 갈 수 있다면
			{
				freq[i] = 1; // 장소 체크
				dfs(i, cost + graph[level][i], cnt + 1); // 장소 번호, 비용, 이동 횟수
				freq[i] = 0;
			}
		}
	}

}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &graph[i][j]);

	dfs(1, 0, 1);
	printf("%d", ans);
	return 0;
}