[백준] 10971 외판원 순회 2 (C++)

백준 10971 외판원 순회 2

1. 문제

문제 링크

2. 접근법

[ 문제 접근 ]

 

백트래킹을 사용하여 푸는 문제이다.

1. 각 도시의 방문 여부를 체크할 배열을 하나 선언한다.

2. 모든 도시를 거쳐 다시 원래의 도시로 돌아와야 하므로 출발 도시를 담을 start 변수를 선언하고 DFS를 돌리면서 start도시와 현재 도시가 같고 모든 도시를 방문한 경우에(cnt로 체크) 최솟값을 업데이트시킨다.

3. DFS가 종료되면 백트래킹을 위해 방문 체크를 해제하고 해당 도시를 방문한 비용을 빼준다.

3. 코드

#include <string>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int n, w[10][10], answer=987654321, sum, start;
bool checked[10];
void DFS(int idx, int cnt)
{
	if (cnt == n&&start==idx)
	{
		answer = min(answer, sum);
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		if (!checked[idx] && w[idx][i] != 0)
		{
			checked[idx] = true;
			sum += w[idx][i];
			//시간 줄임
			if(sum<answer)
				DFS(i, cnt + 1);
			sum -= w[idx][i];
			checked[idx] = false;
		}
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			cin >> w[i][j];

		}
	}
	for (int i = 0; i < n; ++i)
	{
		start = i;
		DFS(i, 0);
	}
	cout << answer << "\n";
	return 0;
}

4. 시간 복잡도

백트래킹을 이용한 방법으로 O(2^N)의 시간 복잡도를 가진다.

5. 결과